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:

CSA (constrained simulated annealing): probabilistic generation of probes in x space, greedy generation in Lagrange-multiplier space, acceptance of probes according to annealing probabilities;
CGA (constrained genetic algorithm): generation of probes in x space by genetic opertors, greedy generation in Lagrange-multiplier space, acceptance of probes according to deterministic rules;
CSAGA (combined constrained simulated annealing and genetic algorithm): generation of probes in x space by probabilistic and genetic opertors, greedy generation in Lagrange-multiplier space, acceptance of probes according to annealing probabilities.

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:

Problem ID	Model File	Data File	Problem Description	Best Solution Found	Tcsa	Tcga	Tcsaga
ODFIT	odfits.mod	N/A	from CUTE benchmark suite	-2380.0	102.63	>400	32.92
S232	s232.mod	N/A	from Schittkowski's suite	-1.0	0.89	1.09	16.89
P2.1	2.1.mod	2.1.dat	from Floudas and Pardalos' suite	-17.0	0.50	5.92	0.50
P2.7.1	2.7.1.mod	2.7.1.dat	from Floudas and Pardalos' suite	-394.75	27.06	155.38	8.23
G1	G1.mod	G1.dat	from EA programming	-15.0	0.56	5.04	0.59
NET2	net2.mod	net2.dat	a transportation networking problem	-1819.0	0.25	3.67	0.18

Tcsa (resp. Tcga and Tcsaga) is the solution time (in seconds on a computer specified at the end of this page) taken by DCS using the basic solver CSA (resp. CGA and CSAGA) to first find a solution of the quality shown in the table above, under the default settings of a random seed of 12 and a constraint-violation tolerance of 1.0e-5.
The time reported above is the shortest time that the best solution is found by the program. The system will continue to call the basic solver at least twice and will only stop if the best solution does not change (within some precision limit). The system will stop after the maximum time limit is exceeded (as specified at the end of this page).
The best solution found by the program may be slightly off from the best known solution of the problem because the constraints are only satisfied to within the specified error tolerance. A tighter error tolerance on constraint satisfaction will lead to better objective values but will take longer time.

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:

Model file. Enter below:
Or upload a file:
Data file. Enter below:
Or upload a file:

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,

Basic solver (see explanation earlier):
Random seed Use default seed of 12 Specify one (1-30000)
The random seed affects the random generation of probes and the trajectory traversed.
Constraint-violation tolerance
This measures the quality of constraint satisfaction in the solution found. Since a solution with a large constraint violation will generally take less time to find, it will be desirable to relax the constraint-violation tolerance for hard-to-satisfy problems or for problems with many equality constraints,

Step 4: Solve the problem

Notes on the Current Implemenation

The software is for solving constrained single-objective NLPs and will not solve unconstrained NLPs or multi-objective NLPs. A problem is considered unconstrained if its variables are constrained by simple bounds after presolve.
The software runs in a single-processor mode on a dual-processor Athlon-MP2000 computer with Solaris x86 5.9.
The DCS daemon allows at most 3 concurrent users, with a CPU time limit of 400 seconds for each user.
The software uses the student version of AMPL preprocessor and can only decode constrained NLPs with no more than 300 variables and 300 constraints after presovle.
Do not include AMPL commands, e.g. "solve;", in your data or model files.

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

Acknowledgments

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