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

Re: ConstrainedMin limited to integer solutions?

• To: mathgroup at smc.vnet.net
• Subject: [mg4560] Re: ConstrainedMin limited to integer solutions?
• From: rubin at msu.edu (Paul A. Rubin)
• Date: Fri, 16 Aug 1996 05:14:57 -0400
• Organization: Michigan State University
• Sender: owner-wri-mathgroup at wolfram.com

In article <4than3$j6e at dragonfly.wolfram.com>,
   Lara Schmidt <lss at ramsey.usno.navy.mil> wrote:
->Does anybody know of a quick way to restrict ConstrainedMin to produce 
->only integer solutions?
->
->________________________________________________________________________
->
-> Lara S. Schmidt     US Naval Observatory        (202)762-1455
-> Mathematician       3450 Massachusetts Ave NW
-> Time Service Dept.  Washington  DC  20392       lss at tycho.usno.navy.mil
->________________________________________________________________________
->
->    USNO GPS Web pages begin at http://tycho.usno.navy.mil/gps.html

Not doable.  ConstrainedMin uses the simplex method (linear programming 
algorithm) and converts everything that can't outrun it to machine 
precision (I *think*) before crunching the problem.  To restrict yourself 
to integer solutions, you need to switch from linear programming to integer 
programming, which means switching from simplex to something like 
branch-&-bound or cutting planes (which would probably use simplex for 
subproblems).  It also means laying in a large supply of NoDoze - IPs are 
frequently a *lot* slower to solve than LPs.  Mathematica does not 
currently contain any IP code, although I think I heard some talk once of 
WRI considering it as a possibility for a future release.  Off-hand, I 
don't know of anyone who's coded an IP package for Mma.  Solving IPs with 
Mma would probably bear a strong resemblance to cleaning all the floors in 
your house with a toothbrush (compact head at that).

Paul

**************************************************************************
* Paul A. Rubin                                  Phone: (517) 432-3509   *
* Department of Management                       Fax:   (517) 432-1111   *
* Eli Broad Graduate School of Management        Net:   RUBIN at MSU.EDU    *
* Michigan State University                                              *
* East Lansing, MI  48824-1122  (USA)                                    *
**************************************************************************
Mathematicians are like Frenchmen:  whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different.                                    J. W. v. GOETHE

==== [MESSAGE SEPARATOR] ====