Discrete optimization

Solving an optimization problem means finding, from a set of solutions that satisfy given constraints, the solution(s) that minimizes (or maximizes) a function measuring the quality of that solution. This function is called the objective function. In general, to model an optimization problem, we start by defining the elements that make up the constraints and the objective function. Some of these elements are known and are called problem parameters. Their values can be read from databases, supplied in files or typed into a computer keyboard. Other elements are unknown and are called unknowns or variables. Constraints and the objective function are expressed using mathematical formulas that combine known parameters and problem variables. The variables often correspond to decisions to be taken in order to obtain the desired optimum. This is known as continuous optimization (see [ ], if the variables representing the decisions take their value on a continuous set of values: for example, all the reals contained between two limits. We speak of discrete optimization if the variables take their value in a finite set or in a countable set, such as the set of integers. In the most general case, some of the variables are continuous and some are discrete. It is the difficulty of problems containing discrete variables that interests us here.

We present four concrete problems and model them using linear or possibly quadratic equations. We then introduce the notions of algorithm and problem complexity. The rest of the dossier is divided into two main parts.

One section is devoted to the presentation of exact solving methods, some of which are polynomial, specific to the "easy" problem under consideration and therefore usable even for large problems; others are pseudo-polynomial and still usable for large problems; finally, exponential methods, built on general schemes, called separation and evaluation procedures can only be used on relatively small problems. It is exponential methods of this type that are used in the general solvers, based on linear programming or constraint propagation, currently available on the software package market. The gradual improvement of these solvers and the spectacular increase in computer speed mean that these software packages can now be used to solve relatively large problems. Nevertheless, execution times still increase exponentially with problem size.

A second part is devoted to approximate solution methods, when we accept that we no longer have proof of obtaining an optimal solution, but hope to use sufficiently clever approaches to obtain very good solutions. In particular, we present the best-known meta-heuristics such as simulated annealing, the Tabu method and genetic algorithms. We also encourage...