"Qu Zhou" <······@cs.cmu.edu> writes:
> Hi,
> Does anybody know where I can find some Lisp code doing integer programming?
> Thanks.
what do you mean by integer programming?
i take it
(+ 2 2)
4
and
(* 2 3)
6
are not what you meant.
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
Don't Fear the Penguin!
"Johan Kullstam" <········@ne.mediaone.net> wrote in message
···················@euler.axel.nom...
> "Qu Zhou" <······@cs.cmu.edu> writes:
>
> > Hi,
> > Does anybody know where I can find some Lisp code doing integer
programming?
> > Thanks.
>
> what do you mean by integer programming?
>
This reeks of a homework assignment, I'd say!
Integer Programming refers to techniques used to solve problems where only
integer variables are meaningful, such as modeling business problems where
an answer like 5.42 is not useful as say, the optimum number of cashiers to
hire.
(disclaimer: my considerable expertise in this area is the result of as much
as 3 minutes spent browsing the results of a Google search. So others may
know even more...)
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
If you're looking for a commercial program, there might be one available
through Ilog CPLEX, www.cplex.org
According to this very clear exposition,
http://mscmga.ms.ic.ac.uk/jeb/or/ip.html , (linear) integer programming,
is optimizing a linear objective function over several variables which
are only allowed to take integer values, subject to inequality or
equality constraints. These are much harder than linear programming
problems with continuous variables. Methods for solving such problems
basically are ways of intelligently searching for the combination of the
integer values maximizing the objective function in such a way as to
avoid trying most of the possible combinations. One basic technique is
called branch and bound and is discussed in the reference above. If you
have access to a simplex method routine (or something fancier) for
solving linear programs, it should be easy to wrap the branch-and-bound
method around it in Lisp. This technique also applies when some of the
variables are discrete and some are continuous.
Other methods, including genetic algorithms, tabu search and simulated
annealing, are also used.
Jeff
"Qu Zhou" <······@cs.cmu.edu> wrote in message
················@cantaloupe.srv.cs.cmu.edu...
> Hi,
> Does anybody know where I can find some Lisp code doing integer
programming?
> Thanks.
>
> Joe Zhou
>
Qu Zhou wrote:
>
> Hi,
> Does anybody know where I can find some Lisp code doing integer programming?
> Thanks.
>
> Joe Zhou
Joe,
Here's what I found:
IPLAN: Planning by Integer Programming
http://www.cs.umd.edu/users/yuan/pkg/iplan/iplan.html
Unfortunately, although IPLAN is written in Common Lisp, the
IP solver is not:
"IPLAN is written in Common Lisp. It requires a common lisp system
to run the instantiation front-end and an AMPL interpreter equiped
with integer programming problem solver such as CPLEX to solve a
planning problem."
I'd suggest contacting ····@cs.umd.edu, the maintainer of the above
web page, to see if he knows of any public domain IP code in Lisp.
Larry
In article <···········@cantaloupe.srv.cs.cmu.edu>, "Qu Zhou"
<······@cs.cmu.edu> wrote:
>Hi,
>Does anybody know where I can find some Lisp code doing integer programming?
>Thanks.
>
>Joe Zhou
Here are some pointers from the recesses of my memory.
I believe it was Bruno Haible that wrote some very nice Common Lisp
code for solving linear programming problems with the simplex
algorithm. I used this code quite a bit in the past and never had
a problem with it. I vaguely recall getting it from the Lisp
repository at CMU (Carnegie Mellon University).
With this code in hand, you can solve purely integral linear
optimization problems using Gomoroy's cut method, and solve
mixed (integral and non-integral) problems using another,
cut-based method. Find a book on (integral) linear optimization
for the details. It's not too hard.
Hope this helps.
Sashank