Web Interface to Discrete Constrained Search

Discrete constrained search (DCS) is a software package for finding constrained global minima (CGM) in the discrete variable space of a single-objective discrete constrained nonlinear programming problem (NLP), with no assumptions on the differentiability and continuity of the objective and constraint functions. NLPs with continuous variable are also solvable using discretized variables.

The method is based on the necessary and sufficient condition for constrained local minima (CLM) in the theory of discrete constrained optimization using Lagrange multipliers developed in our group. The theory proves a one-to-one correspondence between CLM and points satisfying the saddle-point condition in discrete variable space, leading to the first-order necessary and sufficient condition for CLM. Using the theory, a search for CLM is greatly simplified by looking for points that satisfy the saddle-point condition in discrete space, rather than solving the original constrained optimization problem. More information on the theory and applications can be found at our Web site

The current implementation calls a basic solver, using a small amount of allocated time. If the search succeeds to find a CGM, then the process terminates. Otherwise, the time allocated is doubled, and the basic solver is repeated using the extended allocated time. By using iterative deepening, it can be proved that the time to find a CGM is no more than twice the best time to find such a solution.

Each basic solver looks for saddle points in discrete space in the time allocated and differs only in its mechanism of generating and selecting candidate probes. There are three basic solvers available:

Since the CGM is not known ahead of time, the basic solver will be invoked repeatedely until the solution found remains unchanged twice before the search is terminated or until the time limit is exceeded.

Prepare your inputs according to the following instructions and submit your job.

Step 1: Prepare your problem in AMPL format

DCS supports AMPL, A Modeling Language for Mathematical Programming, as the problem input format. Check AMPL homepage for a detailed description of this modeling language. A problem is typically specified by a model file (.mod) and a data file (.dat). Alternatively, you can specify a problem using only a single model file.

Due to limitations in AMPL in modeling arbitrary discrete variables, our current implementation can only solve problems with continuous variables (by discretizing them), without assuming the differentiability and continuity of functions. We are trying to find a work-around in AMPL to model discrete variables at this time.

Here are some sample problems with continuous variables in AMPL you can copy and input:

Step 2: Input your problem and data file (or use sample files from the table above)

Please input your constrained single-objective NLP in AMPL below:

Step 3: Customizing settings (optional). There are very few user-adjustable parameters because the parameters for each basic solver have been set to the best known values, and the iterative-deepening schedule is adjusted dynamically,

Step 4: Solve the problem

Notes on the Current Implemenation

For questions or comments, please send mail to B. Wah or Y. Chen


Research supported by National Aeronautics and Space Administration Grant NCC 2-1230.