MathGroup Archive 2007

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

Search the Archive

Re: Maximize with Integer constraints

  • To: mathgroup at smc.vnet.net
  • Subject: [mg78255] Re: [mg78227] Maximize with Integer constraints
  • From: "Steven Warwick" <warwick at jps.net>
  • Date: Wed, 27 Jun 2007 05:21:31 -0400 (EDT)
  • References: <200706260833.EAA05703@smc.vnet.net> <49779893-9F18-4F8C-B0D8-2EB6F23313A7@mimuw.edu.pl> <468111A3.7060202@wolfram.com>

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: [mg78255] Re: [mg78227] Maximize with Integer constraints


> Andrzej Kozlowski wrote:
>>
>> 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: Book or Manual for 6?
  • Next by Date: Re: Re: problem with Pick
  • Previous by thread: Re: Maximize with Integer constraints
  • Next by thread: Re: Maximize with Integer constraints