Re: Re: Problem with Maximize and conditions.
- To: mathgroup at smc.vnet.net
- Subject: [mg51085] Re: [mg51073] Re: [mg51046] Problem with Maximize and conditions.
- From: DrBob <drbob at bigfoot.com>
- Date: Mon, 4 Oct 2004 06:17:49 -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>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
OK, but that's 65 times slower than a simple search:
Timing[{Floor[x] + Floor[y] +
Floor[z], Floor[{x, y, z}]} /.
Last[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}]]]
{5.187 Second, {43, {20, 4, 19}}}
Timing[feasible = Select[
Flatten[Outer[List, Range[98],
Range[98]], 1] /.
{x_, z_} -> {x, 100 - x/20 -
5*z, z},
1 <= #1[[2]] <= 98 &&
#1[[2]] \[Element] Integers & ];
({Tr[#1], #1} & )[
First[feasible[[Ordering[
feasible, -1,
Tr[#1] > Tr[#2] & ]]]]]]
{0.079 Second, {43, {20, 4, 19}}}
Bobby
On Sun, 3 Oct 2004 05:47:56 -0400 (EDT), Andrzej Kozlowski <akoz at mimuw.edu.pl> 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) â??
>> 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) â??
>>> 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
- 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.