Services & ResourcesWolfram ForumsMathGroup Archive

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

bug in LinearProgramming

• To: mathgroup at smc.vnet.net
• Subject: [mg95487] bug in LinearProgramming
• From: Veit Elser <ve10 at cornell.edu>
• Date: Tue, 20 Jan 2009 05:44:23 -0500 (EST)

This is a re-post because the original did not draw any comments.
The data
c = {1, 1};
m = {{1, 0}, {1, -2}, {-1, 1}};
b = {{1, 0}, {0, 1}, {0, 1}};
lu = {{0, 1}, {0, 1}};
d = {Reals, Reals};
used in
LinearProgramming[c, m, b, lu, d]
corresponds to the problem
minimize x1+x2
subject to the constraints
x1 == 1, x1-2*x2 >= 0, -x1+x2 >= 0
with real variables in the ranges
0 <= x1 <= 1, 0 <= x2 <= 1
It's clear that this problem has no solution, and Mathematica  
recognizes this fact.
But when the domain of x2 is changed to Integers, Mathematica returns  
the "solution"
x1 == 1., x2 == 1
This violates the constraint x1-2*x2 >= 0.

**** earlier posting ****
Here is a simple linear programming problem:

c = {1, 1};
m = {{1, 0}, {1, -2}, {-1, 1}};
b = {{1, 0}, {0, 1}, {0, 1}};
lu = {{0, 1}, {0, 1}};
d = {Reals, Reals};

sol = LinearProgramming[c, m, b, lu, d]

Mathematica 6 returns:

LinearProgramming::"lpsnf" :  "No solution can be found that
satisfies the constraints."

which is obviously correct. But if I change the domain of the second
variable,

d = {Reals, Integers};

then Mathematica gives the solution

sol = {1., 1}. The problem is that

m.sol = {1., -1., 0.}

violates the bound vector b (second component should be greater than 0).
Is there a bug, or am I getting the syntax wrong?

Veit Elser

• Follow-Ups:
  • Re: bug in LinearProgramming
    • From: DrMajorBob <btreat1@austin.rr.com>