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