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.