Re: Re: Problem with Maximize and conditions.
- To: mathgroup at smc.vnet.net
- Subject: [mg51117] Re: [mg51101] Re: Problem with Maximize and conditions.
- From: DrBob <drbob at bigfoot.com>
- Date: Tue, 5 Oct 2004 04:37:03 -0400 (EDT)
- References: <200410020719.DAA26394@smc.vnet.net> <cjoj5g$ap6$1@smc.vnet.net> <200410041018.GAA25229@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
> But it seems you're using brute force. It is nice to see how to use
> brute force when all the other methods works.
The other methods DON'T work. NMinimize, for instance, can't be trusted to return a feasible answer or warn you if it failed, and it may tell you it failed when it actually succeeded.
The two fastest solutions I've seen so far are these:
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.062 Second, {43, {20, 4, 19}}}
Timing[
a = Reduce[{(1/20)*x + y + 5*z ==
100, x \[Element] Integers,
y \[Element] Integers,
z \[Element] Integers, 0 < x < 99,
0 < y < 99, 0 < z < 99},
{x, y, z}]; b = {ToRules[a]};
b[[First[Ordering[x + y + z /.
b, 1]]]]]
{0. Second, {x -> 20, y -> 4, z -> 19}}
The first varies x and z in a brute force manner. The second starts with Reduce to enumerate the entire feasible space and ends with a brute force search for the smallest objective function value.
Bobby
On Mon, 4 Oct 2004 06:18:33 -0400 (EDT), Nacho <ncc1701zzz at hotmail.com> wrote:
> Hello Dr.Bob.
>
> I don't understand very well all thoise # and @ yet ;) I'm on it...
>
> But it seems you're using brute force. It is nice to see how to use
> brute force when all the other methods works.
>
>
> Thanks for your solution.
>
> Best regards.
>
> DrBob <drbob at bigfoot.com> wrote in message news:<cjoj5g$ap6$1 at smc.vnet.net>...
>> Minimize and NMinimize apparently can't solve this simple Integer problem; I'm sure somebody will explain to you why this is a good thing, but I can't.
>>
>> Meanwhile, here's an answer the hard way:
>>
>> Timing[feasible = Select[Flatten[
>> Outer[List, Range@98, Range@98, Range@98], 2], {1/20, 1, 5}.# == 100 &];
>> {Tr@#, #} &@First@feasible[[Ordering[feasible, -1, Tr@#1 > Tr@#2 &]]]]
>>
>> {9.687 Second,{43,{20,4,19}}}
>>
>> and here's a much faster solution:
>>
>> 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.078 Second, {43, {20, 4, 19}}}
>>
>> Bobby
>>
>> On Sat, 2 Oct 2004 03:19:15 -0400 (EDT), Nacho <ncc1701zzz at hotmail.com> wrote:
>>
>> > 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!
>> >
>> >
>> >
>> >
>
>
>
>
--
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: ncc1701zzz@hotmail.com (Nacho)
- Problem with Maximize and conditions.