MathGroup Archive 2003

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

Search the Archive

A bug in ConstrainedMin


I believe there is a bug in ConstrainedMin!

I am asking it to solve a (fairly large) linear program.
It fails to find a solution even though a solution exists.

The linear program is fairly large, so I cannot post it
here. You can download a notebook (about 0.5MB) that contains 
it from

The problem is exact, it involves only rational numbers.
ConstrainedMin should therefore find a solution.

Here are some extracts from the notebook, 
with some explanations:

fun = ... ;
equ = ... ;
var = Array[ ff , {1260} ] ;

Here I define the linear problem. It is composed
of 677 linear equations in 1260 variables.

I then present a solution:

sol = { ... , { ff[1]-> ... , } } ;

To check that sol is a feasible solution I do:


The answer is True which shows that sol does satisfy
all the equations. Then I do:


The answer is 0 which shows that all the variables
are assigned nonnegative values, as required.

All the numbers appearing in fun, equ and sol are rational.
Most of the rationals in sol have huge denominators and numerators.
For example:

ff[1] -> 922901432502320056411751708228635650657588059898\

Next, I try to find a solution to the linear program
using ConstrainedMin:

sol1 = ConstrainedMin[fun,equ,var]; //Timing

After several hours, I get the message:

ConstrainedMin::lpsnf: No solution can be found that satisfies the 

I repeated this several times, in case randomization is
used in the implementation. ConstrainedMin failed four
more times. The running times varied considerably.

I am using version 4.2 of Mathematica for Windows.

Did any one encounter similar problems with ConstrainedMin before?


P.S. I also sent a report to support at

|  Prof. Uri Zwick             |    |
|  Dept. of Computer Science   |  zwick at                   |
|  Tel Aviv University         |                                    |
|  Tel Aviv 69978              |  PHONE: +972 3 6409610             |
|  ISRAEL                      |  FAX:   +972 3 6409357             |

  • Prev by Date: Re: how do i insert a diagram in mathematica?
  • Next by Date: Re: MathKernel access Internet?
  • Previous by thread: Re: Why Plot cannot run under package?
  • Next by thread: RNGs in Mathematica for Experimentation