In this project, a pioneering approach to solve discrete constrained
optimization problems was made to extend the traditional Lagrangian
method (that works in continuous space) in discrete space.
The discrete
Lagrangian method (DLM)
provides the mathematical foundation of
Lagrangian methods that does not exist in existing methods for handling
nonlinear discrete constraints. A key of DLM is the dynamic shift in
emphasis between the objective the constraints, which is controlled by
the adaptive adjustment of Lagrange multipliers in DLM. One of the
major advantages of DLM is that it has very few algorithmic parameters
to be tuned by users. Applying DLM, we have found significant
improvements
in solving
satisfiability problems ,
MAX-SAT problems ,
the design of
multiplierless filter banks ,
and nonlinear integer programming problems.
Dr. Yi Shang, Dept. of Computer Eng./Sci.
Univ. of Missouri, Columbia, MO 65211
(573) 882-3371 Fax: (573) 882-8318
yshang@cecs.missouri.edu, http://www.cecs.missouri.edu/~yshang
Dr. Wah, UIUC
http://manip.crhc.uiuc.edu/research.html