I recall that Hanan Luss and Donald R. Smith around 1986 wrote a series
of articles on optimizing minimax problems without linear programming
(their algorithms were very fast and easy to implement).
One insight they had was that a minimax problem has multiple optimum.
Once you selected the (in the example below) person and the sweet that
has the minimax solution, you can "freeze" that part of the solution and
look for minimax solutions for other people and sweets.
I encourage you (i.e., David Curran) to track down the reference to the
original paper and see if it is applicable. Even if not, you might want
to consider finding the "best" solution that uses as much resources
(sweets) as possible to everyone's benefit.
-Marc Meketon
-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf
Of Oscar Gustafsson
Sent: Wednesday, November 22, 2006 16:14
To: David Curran
Cc: address@hidden
Subject: Re: [Help-glpk] minimax problem
On Wed, 22 Nov 2006, David Curran wrote:
> param sweets: 1 2 3 4 5 6
7
> 8
> Alice 12 18 50 40 20 20
10
> 5
> Bob 5 10 35 30 15 22
30
> 28
If I understand the problem correctly (pseudo-code quite close to
MathProg):
range Kids := Alice, Bob;
range SweetRange := 1..8;
var PickedSweets[Kids]
var WorstSweets;
var SweetsPicks[Kids, SweetRange];
maximize WorstSweets
s.t.(kid in Kids) PickedSweets(kid) >= WorstSweets;
s.t.(kid in Kids) sum(sweet in SweetRange) sweets(kid,
sweet)*SweetsPicke(kid, sweet) = PickedSweets(kid, sweet);
s.t.(sweet in SweetRange) sum(kid in KidsRange) SweetsPicks(kid, sweet)
<=
SweetSupply(sweet);
Regards Oscar
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
------------------------------------------------------------------------
----
This e-mail and any attachments may be confidential or legally
privileged. If you received this message in error or are not the
intended recipient, you should destroy the e-mail message and any
attachments or copies, and you are prohibited from retaining,
distributing, disclosing or using any information contained herein.
Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
------------------------------------------------------------------------
----
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
----------------------------------------------------------------------------