[Date Index]
[Thread Index]
[Author Index]
Re: Problem with Maximize and conditions.
*To*: mathgroup at smc.vnet.net
*Subject*: [mg51073] Re: [mg51046] Problem with Maximize and conditions.
*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>
*Date*: Sun, 3 Oct 2004 05:47:56 -0400 (EDT)
*References*: <200410020719.DAA26384@smc.vnet.net> <4D224676-146C-11D9-BCA4-000A95B4967A@mimuw.edu.pl> <CA5D3844-1470-11D9-BCA4-000A95B4967A@mimuw.edu.pl>
*Sender*: owner-wri-mathgroup at wolfram.com
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/
>>
>
Prev by Date:
**Re: Problem with Maximize and conditions.**
Next by Date:
**Limit problem**
Previous by thread:
**Re: Problem with Maximize and conditions.**
Next by thread:
**Re: Re: Problem with Maximize and conditions.**
| |