MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Integer Linear Programming

  • To: mathgroup at smc.vnet.net
  • Subject: [mg118491] Integer Linear Programming
  • From: Eirik Larsen Følstad <eirik.folstad at q2s.ntnu.no>
  • Date: Fri, 29 Apr 2011 07:35:04 -0400 (EDT)

Hi,

I'm currently using Mathematica 6.0 on a Mac.

When trying to solve the following, Mathematica gives the "LinearProgramming::lpsnf: No solution can be found that satisfies the constraints." as expected;

LinearProgramming[{0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
   0., 0.2,
  0.2}, {{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0,
   0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
   0, -1, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, -1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, -1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0,
   0, 0, 0, 1, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, -1,
   0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, -1}}, {{1.,
   0}, {0., 0}, {0., 0}, {-1., 0}, {1., 0}, {0., 0}, {0., 0}, {-1.,
   0}, {1., -1}, {1., -1}, {1., -1}, {1., -1}, {1., -1}, {1., -1}}, \
{{0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0.,
   1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0.,
   1.}, {0., 1.}, {0., 1.}, {0., 1.}}, Reals]

While when solving the following, Mathematica gives no "fault message", but outputs "{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1}". The only difference from the previous is Integers instead of Reals;


LinearProgramming[{0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
   0., 0.2,
  0.2}, {{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0,
   0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,
   0, -1, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, -1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, -1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0,
   0, 0, 0, 1, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, -1,
   0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, -1}}, {{1.,
   0}, {0., 0}, {0., 0}, {-1., 0}, {1., 0}, {0., 0}, {0., 0}, {-1.,
   0}, {1., -1}, {1., -1}, {1., -1}, {1., -1}, {1., -1}, {1., -1}}, \
{{0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0.,
   1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0., 1.}, {0.,
   1.}, {0., 1.}, {0., 1.}, {0., 1.}}, Integers]

The Integer solution clearly does not satisfy all the constraints given. What is wrong?


Vennlig hilsen / Best regards,
Eirik Larsen F=F8lstad
PhD Candidate
Phone +47 920 44 740
Q2S Centre of Excellence / Norwegian University of Science and Technology
O.S.Bragstads plass 2E /  N-7491 Trondheim / http://www.q2s.ntnu.no






  • Prev by Date: Re: Postfix specification graphics, etc.
  • Next by Date: Dynamic[ImageEffect[CurrentImage[],"Charcoal"]] crashes Mathematica
  • Previous by thread: How to compute a recurrence in 2D using mathematica?
  • Next by thread: Dynamic[ImageEffect[CurrentImage[],"Charcoal"]] crashes Mathematica