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