Neural Networks without Training for Optimization - Neural Networks: Methodology and Applications - page 444

• some variables;

• an objective, which is a function of the variables, and is generally expressed

as the minimization of a cost, or a set of costs, of the solution;

• some constraints to be satisfied by the solution. Some are essential; then

they are named strict constraints. Other ones express some preferences;
then they are named relaxable constraints.

The problem is then to find, in a limited time, a set of variable values
that reach the objective while satisfying the constraints. Depending on the
applications, the number of optimisation variables ranges from a few to hun-
dreds of thousands, and the expected response time from a few microseconds
to several hours. Moreover, it is sometimes desirable to find a set of solutions
among which the user will make a choice.
The variables of an optimisation problem can be

• continuous variables,

• discrete variables, e.g. binary variables (the problem is said to be combi-

natorial),

• mixed variables, i.e., some variables are continuous while others are dis-

crete (those problems are said to be mixed).

A problem, besides, may not contain constraints, or cost function to be op-
timised. In that last case, the question is then related to the existence of a
solution satisfying all the constraints; such a problem is named constraint
satisfaction problem. When all constraints cannot be satisfied, i.e., when the
problem has no solution, it is sometimes interesting to find a satisfactory
trade-off that violates a few relaxable constraints.
The cost functions to be optimised can be expressed with various for-
mulations, more or less complex, e.g. as linear or quadratic functions of the
variables.
Sometimes, the data necessary to solve the optimisation problem are not
immediately available, but may become available gradually: the methods must
then update dynamically the solutions.
Finally, some problems are distributed: some locally connected decision
centres make partial decisions according to the available local data, and that
set of local decisions must be a good solution of the global problem.

8.1.1 Examples

There is a very large variety of combinatorial optimisation problems. They
are commonly encountered in many industrial applications. Among them, the
author has been directly involved in the following typical areas:

• Military: resource allocation problems (weapon allocation on moving tar-

gets [Herault 1995a,b,c]), target tracking [Herault 1997a].