MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Problem with Maximize and conditions.
  • Next by Date: Re: A way around the limitations of Re[] and Im[]
  • Previous by thread: Re: Problem with Maximize and conditions.
  • Next by thread: Problem with Maximize and conditions.