Re: Maximize with Integer constraints
- To: mathgroup at smc.vnet.net
- Subject: [mg78263] Re: [mg78227] Maximize with Integer constraints
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Wed, 27 Jun 2007 05:25:37 -0400 (EDT)
- References: <200706260833.EAA05703@smc.vnet.net> <49779893-9F18-4F8C-B0D8-2EB6F23313A7@mimuw.edu.pl> <468111A3.7060202@wolfram.com> <042b01c7b7fb$de9528a0$c00aa8c0@L33D5A6>
- Reply-to: adams at wolfram.com
Exact optimization algorithms are used by Maximize with exact inputs.
If you use NMaximize or inexact inputs, you get numeric algorithms.
With Maximize and exact inputs your examples get solved correctly.
(Note that exact computations respect strict inequalities, so the
answer to the first four examples is 20 not 24).
And yes, the NMaximize examples giving wrong answers have been filed
as a bug report.
In[1]:= Maximize[
{x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
x1 < 5 &&
x2 < 8 &&
x3 < 9 &&
x4 < 2},
{x1, x2, x3, x4}]
Out[1]= {20, {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
In[2]:= Maximize[
{x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
0 < x1 < 5 &&
0 < x2 < 8 &&
0 < x3 < 9 &&
0 < x4 < 2},
{x1, x2, x3, x4}]
Out[2]= {20, {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
In[3]:= Maximize[
{x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
1/10 < x1 < 5 &&
0 < x2 < 8 &&
0 < x3 < 9 &&
0 < x4 < 2},
{x1, x2, x3, x4}]
Out[3]= {20, {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
In[4]:= Maximize[
{x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
-1/10 < x1 < 5 &&
0 < x2 < 8 &&
0 < x3 < 9 &&
0 < x4 < 2},
{x1, x2, x3, x4}]
Out[4]= {20, {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
In[5]:= Maximize[
{x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
x1 < 51/10 &&
x2 < 8 &&
x3 < 9 &&
x4 < 2},
{x1, x2, x3, x4}]
Out[5]= {21, {x1 -> 5, x2 -> 7, x3 -> 8, x4 -> 1}}
Best Regards,
Adam Strzebonski
Wolfram Research
Steven Warwick wrote:
> is something more obscure is going on? the following tests seem to
> contradict comments on integer vs. real constraints.
>
> note also the effect of negative numbers....
>
> do things like this get passed on as bugs to the design team?
>
> In[19]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> x1 < 5 &&
> x2 < 8 &&
> x3 < 9 &&
> x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[19]= {0., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0}} NO!
>
> In[20]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> 0 < x1 < 5 &&
> 0 < x2 < 8 &&
> 0 < x3 < 9 &&
> 0 < x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[20]= {0., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0}} NO!
>
> In[21]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> 0.1 < x1 < 5 &&
> 0 < x2 < 8 &&
> 0 < x3 < 9 &&
> 0 < x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[21]= {24., {x1 -> 5, x2 -> 8, x3 -> 9, x4 -> 2}} YES!
>
> In[22]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> -0.1 < x1 < 5 &&
> 0 < x2 < 8 &&
> 0 < x3 < 9 &&
> 0 < x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[22]= {0., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0}} NO!
>
> In[23]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> 1/10 < x1 < 5 &&
> 0 < x2 < 8 &&
> 0 < x3 < 9 &&
> 0 < x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[23]= {24., {x1 -> 5, x2 -> 8, x3 -> 9, x4 -> 2}} YES!
>
> In[24]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> -1/10 < x1 < 5 &&
> 0 < x2 < 8 &&
> 0 < x3 < 9 &&
> 0 < x4 < 2},
> {x1, x2, x3, x4}]
>
> Out[24]= {0., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0}} NO!
>
> In[25]:= NMaximize[
> {x1 + x2 + x3 + x4, Element[{x1, x2, x3, x4}, Integers ] &&
> x1 < 5.1 &&
> x2 < 8 &&
> x3 < 9 &&
> x4 < 2},
> {x1, x2, x3, x4}]
> Out[25]= {0., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 0}} NO!
>
>
>
> ----- Original Message -----
> From: "Adam Strzebonski" <adams at wolfram.com <mailto:adams at wolfram.com>>
> To: "Andrzej Kozlowski" <akoz at mimuw.edu.pl <mailto:akoz at mimuw.edu.pl>>
> Cc: "sdw" <warwick at jps.net <mailto:warwick at jps.net>>;
> <mathgroup at smc.vnet.net <mailto:mathgroup at smc.vnet.net>>
> Sent: Tuesday, June 26, 2007 9:16 AM
> Subject: Re: [mg78227] Maximize with Integer constraints
>
> > Andrzej Kozlowski wrote:
> >> *This message was transferred with a trial version of
> CommuniGate(tm) Pro*
> >>
> >> On 26 Jun 2007, at 17:33, sdw wrote:
> >>
> >>>
> >>> given entry #1:
> >>>
> >>>
> >>> Maximize[
> >>> {x1 + x2 + x3 + x4,
> >>> Element[x1 | x2 | x3 | x4 , Integers] &&
> >>> 0 <= x1 <= 5.6 &&
> >>> 0 <= x2 <= 8.6 &&
> >>> 0 <= x3 <= 9.7 &&
> >>> 4.0 <= x4 <= 22.4 }, {x1, x2, x3, x4}]
> >>>
> >>> {4., {x1 -> 0, x2 -> 0, x3 -> 0, x4 -> 4}}
> >>>
> >>> note - zeros for answers
> >>> entry #2:
> >>> Maximize[
> >>> {x1 + x2 + x3 + x4,
> >>> Element[x1 | x2 | x3 | x4 , Integers] &&
> >>> 0 <= x1 <= 5.6 &&
> >>> 0 <= x2 <= 8.6 &&
> >>> 0 <= x3 <= 9.7 &&
> >>> 4.1 <= x4 <= 22.4 }, {x1, x2, x3, x4}]
> >>>
> >>> {44., {x1 -> 5, x2 -> 8, x3 -> 9, x4 -> 22}}
> >>>
> >>> note good answers...
> >>> only difference is 4.1 vs. 4 in constraints
> >>> any ideas what is going on?
> >>>
> >>> thanks,
> >>>
> >>> sdw
> >>>
> >>>
> >>
> >> This is probably a bug, but in any case, since Maximize uses exact
> >> algebraic methods it is not a good idea to have approximate numbers in
> >> input. Rationalizing your first input will produce the right answer:
> >>
> >> Maximize[{x1 + x2 + x3 + x4, Element[x1 | x2 | x3 | x4, Integers] &&
> >> Rationalize[0 <= x1 <= 5.6 && 0 <= x2 <= 8.6 && 0 <= x3 <= 9.7 &&
> >> 4. <= x4 <= 22.4]}, {x1, x2, x3, x4}]
> >> {44, {x1 -> 5, x2 -> 8, x3 -> 9, x4 -> 22}}
> >>
> >> Andrzej Kozlowski
> >>
> >
> > When inexact numbers are present in the input, Maximize simply passes
> > the problem to NMaximize. NMaximize uses numeric methods and is not
> > guaranteed to find the global maximum (though in this example it
> > probably should do better). To use exact optimization methods you need
> > to make sure that the input given to Maximize is exact.
> >
> > As Andrzej Kozlowski has shown, inexact expressions can be converted to
> > exact ones using Rationalize. An issue worth remembering here is that
> > one-argument Rationalize converts only inexact numbers that are "close"
> > to rationals.
> >
> > In[1]:= Rationalize[{0.5, 3.1415927}]
> >
> > 1
> > Out[1]= {-, 3.14159}
> > 2
> >
> > Rationalize[expr, 0] converts all inexact numbers in expr.
> >
> > In[2]:= Rationalize[{0.5, 3.1415927}, 0]
> >
> > 1 31415927
> > Out[2]= {-, --------}
> > 2 10000000
> >
> >
> > Best Regards,
> >
> > Adam Strzebonski
> > Wolfram Research
> >
- References:
- Maximize with Integer constraints
- From: "sdw" <warwick@jps.net>
- Maximize with Integer constraints