MathGroup Archive 2004

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

Search the Archive

Re: Re: Problem with Maximize and conditions.

  • To: mathgroup at smc.vnet.net
  • Subject: [mg51093] Re: [mg51053] Re: [mg51046] Problem with Maximize and conditions.
  • From: DrBob <drbob at bigfoot.com>
  • Date: Mon, 4 Oct 2004 06:18:09 -0400 (EDT)
  • References: <200410020719.DAA26384@smc.vnet.net> <200410030947.FAA10649@smc.vnet.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

>> but what really puzzles me is that giving NMinimize the correct
>> solution as an initial point does not seem to help

And it gives an infeasible answer without an error message, while in another recent problem, it gave a right answer WITH an error message (falsely saying it couldn't find a feasible point).

Bobby

On Sun, 3 Oct 2004 05:47:19 -0400 (EDT), Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote:

> On 2 Oct 2004, at 16:19, Nacho wrote:
>
>> *This message was transferred with a trial version of CommuniGate(tm)
>> Pro*
>> Hello.
>>
>> I was trying to solve a problem with Mathematica 5 and I am getting
>> strange results.
>>
>> The problem is:
>>
>> Minimize x+y+z, with the condition that 1/20x+y+5z==100 and x,y,z are
>> Integers between 1 and 98 (inclusive).
>>
>> So I use:
>>
>> Minimize[{x+y+z, 1/20 x+y+5z\[Equal]100,  x \[Element] Integers,
>>     y \[Element] Integers, z\[Element]Integers, 0<x<99,0<y<99,0<z<99},
>> {x,y,
>>     z}]
>>
>> I have copied the text using "Plain text" option, I hope it's fine.
>>
>> This returns the same expression, I suppose that Mathematica cannot
>> resolve it. So I use NMinimize:
>>
>> NMinimize[{x+y+z, 1/20 x+y+5z\[Equal]100,  x \[Element] Integers,
>>     y \[Element] Integers, z\[Element]Integers, 0<x<99,0<y<99,0<z<99},
>> {x,y,
>>     z}]
>>
>> Now I get a result, but rather weird...
>>
>> \!\({25.`, {x -> 1, y -> 5, z -> 1899\/100}}\)
>>
>> The minimum of x+y+z is 25 but z is 1899/100
>> 1899/100 is not a Integers, and the nearest Integer, 19, doesn't
>> satisfy 1/20x+y+5z==100, and also x+y+z is not 25 but 24.99
>>
>> I don't know why Mathematica has returned a Real when I specified an
>> Integers. I suppose that it is related to the use of NMinimize. I
>> suppose that it considers that 18.99 is so near of 19 that it can be
>> considered an Integer.
>>
>> If you remove the condition of z being an Integer, the result changes,
>> so it is affecting. Also, if you ask for "1899/100 e Integers" it
>> returns False.
>>
>> So, does anybody know how to solve this? Ideally, I would like to know
>> why Minimize doesn't work (so I have to use NMinimize), but in any
>> case, how to solve the problem.
>>
>> Thanks!
>>
>>
> First, let us solve the problem.
>
>
> In[1]:=
> p = List @@ Apply[List, Reduce[{(1/20)*x + y + 5*z == 100, 0 < x < 99,
> 0 < y < 99, 0 < z < 99},
>       {x, y, z}, Integers], {1}]
>
> Out[1]=
> {{x == 20, y == 4, z == 19}, {x == 20, y == 9, z == 18}, {x == 20, y ==
> 14, z == 17},
>    {x == 20, y == 19, z == 16}, {x == 20, y == 24, z == 15}, {x == 20, y
> == 29, z == 14},
>    {x == 20, y == 34, z == 13}, {x == 20, y == 39, z == 12}, {x == 20, y
> == 44, z == 11},
>    {x == 20, y == 49, z == 10}, {x == 20, y == 54, z == 9}, {x == 20, y
> == 59, z == 8},
>    {x == 20, y == 64, z == 7}, {x == 20, y == 69, z == 6}, {x == 20, y
> == 74, z == 5},
>    {x == 20, y == 79, z == 4}, {x == 20, y == 84, z == 3}, {x == 20, y
> == 89, z == 2},
>    {x == 20, y == 94, z == 1}, {x == 40, y == 3, z == 19}, {x == 40, y
> == 8, z == 18},
>    {x == 40, y == 13, z == 17}, {x == 40, y == 18, z == 16}, {x == 40, y
> == 23, z == 15},
>    {x == 40, y == 28, z == 14}, {x == 40, y == 33, z == 13}, {x == 40, y
> == 38, z == 12},
>    {x == 40, y == 43, z == 11}, {x == 40, y == 48, z == 10}, {x == 40, y
> == 53, z == 9},
>    {x == 40, y == 58, z == 8}, {x == 40, y == 63, z == 7}, {x == 40, y
> == 68, z == 6},
>    {x == 40, y == 73, z == 5}, {x == 40, y == 78, z == 4}, {x == 40, y
> == 83, z == 3},
>    {x == 40, y == 88, z == 2}, {x == 40, y == 93, z == 1}, {x == 60, y
> == 2, z == 19},
>    {x == 60, y == 7, z == 18}, {x == 60, y == 12, z == 17}, {x == 60, y
> == 17, z == 16},
>    {x == 60, y == 22, z == 15}, {x == 60, y == 27, z == 14}, {x == 60, y
> == 32, z == 13},
>    {x == 60, y == 37, z == 12}, {x == 60, y == 42, z == 11}, {x == 60, y
> == 47, z == 10},
>    {x == 60, y == 52, z == 9}, {x == 60, y == 57, z == 8}, {x == 60, y
> == 62, z == 7},
>    {x == 60, y == 67, z == 6}, {x == 60, y == 72, z == 5}, {x == 60, y
> == 77, z == 4},
>    {x == 60, y == 82, z == 3}, {x == 60, y == 87, z == 2}, {x == 60, y
> == 92, z == 1},
>    {x == 80, y == 1, z == 19}, {x == 80, y == 6, z == 18}, {x == 80, y
> == 11, z == 17},
>    {x == 80, y == 16, z == 16}, {x == 80, y == 21, z == 15}, {x == 80, y
> == 26, z == 14},
>    {x == 80, y == 31, z == 13}, {x == 80, y == 36, z == 12}, {x == 80, y
> == 41, z == 11},
>    {x == 80, y == 46, z == 10}, {x == 80, y == 51, z == 9}, {x == 80, y
> == 56, z == 8},
>    {x == 80, y == 61, z == 7}, {x == 80, y == 66, z == 6}, {x == 80, y
> == 71, z == 5},
>    {x == 80, y == 76, z == 4}, {x == 80, y == 81, z == 3}, {x == 80, y
> == 86, z == 2},
>    {x == 80, y == 91, z == 1}}
>
> This gives all the integer solutions of your set of equations. Now lets
> find which one ahs the minimum value:
>
> In[2]:=
> Ordering[x + y + z /. {ToRules[Reduce[{(1/20)*x + y + 5*z == 100, 0 < x
> < 99, 0 < y < 99, 0 < z < 99},
>        {x, y, z}, Integers]]}]
>
> Out[2]=
> {1, 2, 3, 4, 5, 20, 6, 21, 7, 22, 8, 23, 9, 24, 10, 39, 25, 11, 40, 26,
> 12, 41, 27, 13, 42, 28, 14,
>    43, 29, 15, 58, 44, 30, 16, 59, 45, 31, 17, 60, 46, 32, 18, 61, 47,
> 33, 19, 62, 48, 34, 63, 49, 35,
>    64, 50, 36, 65, 51, 37, 66, 52, 38, 67, 53, 68, 54, 69, 55, 70, 56,
> 71, 57, 72, 73, 74, 75, 76}
>
> This means its the first one. The values of the variables where the
> minimum was found are:
>
> p[[1]]
>
>
> {x == 20, y == 4, z == 19}
>
> The minimum value is:
>
>
> Plus @@ p[[1,All,2]]
>
>
> 43
>
> So rather larger than 25.
>
> Now, as for the other part. Well, the methods used by Minimize are
> quite unable to dealwith integer problems and the methods used by
> NMinimize are, say, not terribly good. Basically you have to try to
> adjust various options in NMinimize and see if you can get a better
> result. One problem is, of course, that it is hard to know how "good'
> the answer you are getting is. The other problem is that the options
> used by NMinimize are not terribly well documented, so you have to do
> some guessing.
>
> By trying various options the best I have been able to do is
>
>
> NMinimize[{x + y + z, (1/20)*x + y + 5*z == 100, (x | y | z) â??
> Integers, 0 < x < 99, 0 < y < 99,
>     0 < z < 99}, {x, y, z}, Method -> {"DifferentialEvolution",
> "ScalingFactor" -> 0,
>      "PenaltyFunction" -> (100*(#1 - Floor[#1]) & )}]
>
> {42., {x -> 20, y -> 3, z -> 96/5}}
>
> which is not bad.
>
> but what really puzzles me is that giving NMinimize the correct
> solution as an initial point does not seem to help;
>
>
> NMinimize[{x + y + z, (1/20)*x + y + 5*z == 100, (x | y | z) â??
> Integers, 0 < x < 99, 0 < y < 99,
>     0 < z < 99}, {x, y, z}, Method -> {"DifferentialEvolution",
> "ScalingFactor" -> 0,
>      "PenaltyFunction" -> (100*(#1 - Floor[#1]) & ), InitialPoints ->
> {{20, 4, 19}}}]
>
> {42., {x -> 20, y -> 3, z -> 96/5}}
>
> ????
>
>
>
>
> Andrzej Kozlowski
> Chiba, Japan
> http://www.akikoz.net/~andrzej/
> http://www.mimuw.edu.pl/~akoz/
>
>
>
>



-- 
DrBob at bigfoot.com
www.eclecticdreams.net


  • Prev by Date: Re: Problem with Maximize and conditions.
  • Next by Date: Re: Re: Problem with Maximize and conditions.
  • Previous by thread: Re: Problem with Maximize and conditions.
  • Next by thread: Re: Problem with Maximize and conditions.