Re: Re: Problem with Maximize and conditions.
- To: mathgroup at smc.vnet.net
- Subject: [mg51083] Re: [mg51073] Re: [mg51046] Problem with Maximize and conditions.
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 4 Oct 2004 06:17:43 -0400 (EDT)
- References: <200410020719.DAA26384@smc.vnet.net> <4D224676-146C-11D9-BCA4-000A95B4967A@mimuw.edu.pl> <CA5D3844-1470-11D9-BCA4-000A95B4967A@mimuw.edu.pl> <200410030947.FAA10750@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Just as a curiosity, here is a solution using Minimize:
First[Sort[Table[Minimize[{i + y + z,
(1/20)*i + y + 5*z == 100, (y | z) $B":(B Integers,
0 < y < 99, 0 < z < 99}, {y, z}], {i, 1, 99}]]]
{43, {y -> 4, z -> 19}}
In fact, however, Minimize is not a good tool for this sort of
problems. It's main purpose is minimizing polynomial expressions with
polynomial constraints and its basic tool is CAD (Cylindrical Algebraic
Decomposition). This only works over the real numbers.It also uses
LinearProgramming to deal with the linear case.
Minimize can also solve some integer programming problems. It is not
clear to me what methods it uses but they seem to be very rudimentary.
The problem with NMinimize is different. Numerical optimization should
always produce the right answer given a sufficient number of search
points so there seems to be really something wrong here. (On the other
hand one can never know what "sufficient number of search points" is.
Andrzej Kozlowski
On 3 Oct 2004, at 18:47, Andrzej Kozlowski wrote:
> I have thought of another approach which seems to work better. The idea
> is simply to give up the requirement that the numbers we are searching
> for are integers and instead express the conditions in terms of Floor[]
> (or IntegerPart). By taking
> DifferentialEvolution now returns the correct answer provided we use
> enough SearchPoints.
>
>
>
> NMinimize[{Floor[x] + Floor[y] + Floor[z], (1/20)*Floor[x] + Floor[y] +
> 5*Floor[z] == 100, 1 <= x <= 99, 1 <= y <= 99, 1 <= z <= 99},
> {x, y, z}, Method -> {"DifferentialEvolution", SearchPoints -> 250}]
>
>
> {43., {x -> 20.92250459337014, y -> 4.342462850628164, z ->
> 19.98314126097282}}(Taking Floor again we obtain integer answers).
>
> It now performs much better than SimulatedAnnealing, which seems to
> require a lot more SearchPoints and takes very much longer.
>
> Andrzej Kozlowski
>
> On 2 Oct 2004, at 21:44, Andrzej Kozlowski wrote:
>
>> 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)
- Re: Problem with Maximize and conditions.
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Problem with Maximize and conditions.