A bug in ConstrainedMin

• To: mathgroup at smc.vnet.net
• Subject: [mg39614] A bug in ConstrainedMin
• From: Uri Zwick <zwick at tau.ac.il>
• Date: Wed, 26 Feb 2003 02:41:59 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

```
Hi,

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
it from http://www.cs.tau.ac.il/~zwick/lp.nb

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:

Apply[And,equ/.sol[[2]]]

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

Min[var/.sol[[2]]]

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\
04896470687513401138347512782442343739094390553089976178624872763307060585643\
216605600038980696181/1850340673700727458229284390321328589448054145133757190\
14800687943645293037058114246232231552323986716620480274258767396357073424003\
962926789008310

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
constraints.

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?

Uri

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

---------------------------------------------------------------------
|  Prof. Uri Zwick             |  http://www.cs.tau.ac.il/~zwick    |
|  Dept. of Computer Science   |  zwick at tau.ac.il                   |
|  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