Re: Problem with Maximize and conditions.
- To: mathgroup at smc.vnet.net
- Subject: [mg51054] Re: [mg51046] Problem with Maximize and conditions.
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sun, 3 Oct 2004 05:47:21 -0400 (EDT)
- References: <200410020719.DAA26384@smc.vnet.net> <4D224676-146C-11D9-BCA4-000A95B4967A@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
I have finally managed to get NMinimize return the right answer:
NMinimize[{x + y + z, (1/20)*x + y + 5*z == 100, (x | y | z) $B":(B
Integers, 0 < x < 99, 0 < y < 99,
0 < z < 99}, {x, y, z}, Method -> {"SimulatedAnnealing",
"PenaltyFunction" ->
(100*(#1 - Floor[#1]) & ), SearchPoints -> 250}, MaxIterations ->
500]
{43., {x -> 20, y -> 4, z -> 19}}
I am not sure if all the options, particularly MaxIterations, are
needed. This would need more testing. According to the help
"DifferentialEvolution" ought to be best for problems involving
integers, but not matter what I do to it I can't force it to return the
right answer.
Andrzej
On 2 Oct 2004, at 21:12, Andrzej Kozlowski 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) $B":(B
> 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) $B":(B
> 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/
>
- References:
- Problem with Maximize and conditions.
- From: ncc1701zzz@hotmail.com (Nacho)
- Problem with Maximize and conditions.