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 here. You can download a notebook (about 0.5MB) that contains 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 | ---------------------------------------------------------------------