Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Maximize with Integer constraints

  • To: mathgroup at smc.vnet.net
  • Subject: [mg78334] Re: [mg78227] Maximize with Integer constraints
  • From: Brett Champion <Brettc at wolfram.com>
  • Date: Thu, 28 Jun 2007 04:33:59 -0400 (EDT)
  • References: <200706260833.EAA05703@smc.vnet.net> <49779893-9F18-4F8C-B0D8-2EB6F23313A7@mimuw.edu.pl> <468111A3.7060202@wolfram.com> <042b01c7b7fb$de9528a0$c00aa8c0@L33D5A6> <5B6430C1-E386-4EDD-B950-0F7040974001@mimuw.edu.pl>

On Jun 26, 2007, at 9:55 PM , Andrzej Kozlowski wrote:

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

DifferentialEvolution is definitely used for nonlinear integer  
optimization problems.  Something else is (poorly) handling the  
linear integer problems.

Brett Champion
Wolfram Research

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



  • Prev by Date: Re: Re: problem with Pick
  • Next by Date: Quick and dirty Zooming tool
  • Previous by thread: Re: Maximize with Integer constraints
  • Next by thread: Re: Maximize with Integer constraints