Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Problem with Maximize and conditions.

• To: mathgroup at smc.vnet.net
• Subject: [mg51213] Re: Problem with Maximize and conditions.
• From: p-valko at tamu.edu (Peter Valko)
• Date: Fri, 8 Oct 2004 02:55:17 -0400 (EDT)
• References: <cjlna7$q7f$1@smc.vnet.net> <cjoiig$alt$1@smc.vnet.net> <cjr9ea$ost$1@smc.vnet.net> <200410050837.EAA08385@smc.vnet.net> <ck0b8c$nr7$1@smc.vnet.net> <ck33j9$av4$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Hi,

Of course Steve was the one who solved the problem by introducing
Reduce. Using it inside the Minimize command is a smart move, but it
does not change the fact: the reduce function explicitely prepares the
whole set of feasible solutions.
As Janos Pinter and others have pointed out, complete enumeration
works for the little example in question, but it cannot be used for
larger problems.
 

To get a bit nearer to the root of the problem I rewrote the original
example as

Minimize[{x + y + z, {1/20 x + y + 5z ≥ 100, 1/20 x + y + 5z
≤ 102, x
          ∈ Integers, y ∈ Integers, z ∈ Integers, 0
< x < 99, 0 <
        y < 99, 0 < z < 99}}, {x, y, z}] 

This works fine and gives the correct solution
{22, {x -> 1, y -> 1, z -> 20}}

Unfortunately, when I make the second inequality stronger, that is
1/20 x + y + 5z &#8804; 101

then "MathKernel encounters a problem and has to close (while being
sorry for the inconvenience.)"

Appearantly, Minimize uses the Gomory-algorithm, reducing the integer
LP into a series of classical LP problems, but somewhere on the road
it crashes. This is a simple bug and I think the given example will
help the developer to find it.

Regards
Peter

 
"Steve Luttrell" <steve_usenet at _removemefirst_luttrell.org.uk> wrote in message news:<ck33j9$av4$1 at smc.vnet.net>...
> Yes, I knew that, because my first reply listed the full output of Reduce! 
> However, I overlooked the possibility that immediately substituting this 
> output back into Minimize would work.
> 
> Steve Luttrell
> 
> "Andrzej Kozlowski" <akoz at mimuw.edu.pl> wrote in message 
> news:ck0b8c$nr7$1 at smc.vnet.net...
> >
> > On 5 Oct 2004, at 17:37, Steve Luttrell wrote:
> >
> >> It seems
> >> that the conditions you feed to Minimize are "improved" by being
> >> wrapped in
> >> Reduce.
> >>
> >
> > Well, they are not just "improved" but actually "Reduced" to
> > triviality. Reduce does all the work and Minimize is only left with
> > something that looks like this (except that with more terms)
> >
> >
> > Minimize[x + y + z, {x == 20 && y == 4 && z == 19 ||
> >     x == 20 && y == 9 && z == 18}, {x, y, z}]
> >
> >
> > This sort of thing even Minimize can manage;-)
> >
> >
> > Andrzej Kozlowski
> > Chiba, Japan
> > http://www.akikoz.net/~andrzej/
> > http://www.mimuw.edu.pl/~akoz/
> >

• Follow-Ups:
  • Re: Re: Problem with Maximize and conditions.
    • From: DrBob <drbob@bigfoot.com>

• References:
  • Re: Problem with Maximize and conditions.
    • From: "Steve Luttrell" <steve_usenet@_removemefirst_luttrell.org.uk>