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.

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:

- T
*csa*(resp. T*cga*and T*csaga*) 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.

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 |

Notes:

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

- 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.