Unbelievable bug in ConstrainedMin, ConstrainedMax and LinearProgramming

*To*: mathgroup at smc.vnet.net*Subject*: [mg40206] Unbelievable bug in ConstrainedMin, ConstrainedMax and LinearProgramming*From*: Uri Zwick <zwick at tau.ac.il>*Date*: Tue, 25 Mar 2003 14:50:58 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

Hi, I sent several previous messages complaining about bugs in ConstrainedMin. All my previous examples, however, were fairly complicated. Here are extremely simple examples that show that ConstrainedMin, ConstrainedMax and LinearProgramming all contain a very basic flaw: In[1] := ConstrainedMin[ x , {x==1,x==2} , {x} ] Out[1] = {2, {x->2}} In[1] := ConstrainedMax[ x , {x==1,x==2} , {x} ] ConstrainedMax::"lpsub": "The problem is unbounded." Out[2] = {Infinity, {x -> Indeterminate}} The same problems occur when using LinearProgramming instead of ConstrainedMin and ConstrainedMax: In[3] := LinearProgramming[{1}, {{1}, {1}}, {{1, 0}, {2, 0}}] Out[3] = {2} In[4] := LinearProgramming[{-1}, {{1}, {1}}, {{1, 0}, {2, 0}}] ConstrainedMax::"lpsub": "The problem is unbounded." Out[4] = {Indeterminate} It seems that these three linear programming functions have a basic difficulty in handling equalities! The documentation of these functions explicitly allow equalities: "ConstrainedMax accepts both strict inequalities of the form lhs < rhs, and nonstrict ones of the form lhs <= rhs. It also accepts equalities of the form lhs == rhs." "LinearProgramming[c, m, {{b1,s1},{b2,s2},...}] finds a vector x which minimizes c.x subject to a and linear constraints specified by the matrix m and the pairs {bi,si}. For each row mi of m, the corresponding constraint is mi>=bi if si>0, or mi==bi if si==0, or mi<=bi if ai<0." (Ironically, there is also a bug in this description, mi>=bi, mi==bi and mi<=bi should of course be mi.x>=bi, mi.x==bi and mi.x<=bi ...) The above behavior is observed under Mathematica 4.2 for Windows, Mathematica 4.2 for SGI IRIX, Mathematica 4.2 for Sun Solaris, and Mathematica 4.1 for LINUX. A correct answer is obtained, at least in these simple cases, if an equality mi.x==bi is replaced by the two inequalities mi.x>=bi and mi.x<=bi: In[5] := ConstrainedMin[ x , {x<=1,x>=1,x<=2,x>=2} , {x} ] ConstrainedMax::"lpsnf": "No solution can be found that satisfies the constraints." Out[5] = ConstrainedMin[ x , {x<=1,x>=1,x<=2,x>=2} , {x} ] However, ConstrainedMin, and probably also ConstrainedMax and LinearProgramming, does occasionally give wrong answers even when no equalities are present! See one of my previous posting to this group. In view of all this, I reiterate the question I raised in a separate posting: Is there an official list of all known problems with Mathematica? It would be a shame if other users of Mathematica would have to waste as much time as I did to (re)discover this or other known bugs. Best regards, Uri --------------------------------------------------------------------- | 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 | ---------------------------------------------------------------------