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