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

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