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>