Re: Maximize with Integer constraints
- To: mathgroup at smc.vnet.net
- Subject: [mg78287] Re: [mg78227] Maximize with Integer constraints
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 27 Jun 2007 05:37:55 -0400 (EDT)
- References: <200706260833.EAA05703@smc.vnet.net> <49779893-9F18-4F8C-B0D8-2EB6F23313A7@mimuw.edu.pl> <468111A3.7060202@wolfram.com> <042b01c7b7fb$de9528a0$c00aa8c0@L33D5A6>
These problems seem to go away when "DiffierentialEvolution" is used
explicitly as the maximization method:
NMaximize[{x1 + x2 + x3 + x4,
Element[{x1, x2, x3, x4}, Integers] && x1 < 5 &&
x2 < 8 && x3 < 9 && x4 < 2}, {x1, x2, x3, x4},
Method -> "DifferentialEvolution"]
{20., {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
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}, Method -> "DifferentialEvolution"]
{20., {x1 -> 4, x2 -> 7, x3 -> 8, x4 -> 1}}
Now, what seems really strange about this (to me) is that I have
always believed that DifferentialEvolution was the method of choice
for integer optimization problems??
Andrzej Kozlowski
On 26 Jun 2007, at 23:11, 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>
> To: "Andrzej Kozlowski" <akoz at mimuw.edu.pl>
> Cc: "sdw" <warwick at jps.net>; <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