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

polynomially with the number of variables. A number of methods were found
to solve e ciently this type of problems [Schrijver 1986], the most famous
one being the simplex (which has already been mentioned in the theoretical
and algorithmic addenda of Chap. 2, to put the dynamic models under a
canonical form). Nevertheless, when the number of variables becomes very
high, the simplex is very slow; other methods, such as the interior points
methods, avoid that drawback [Gonzaga 1992].
Practically, it is sometimes necessary to linearise some problems which
are non-linear. Nevertheless, the resulting modelling error can be large: it is
then necessary to use other methods, which can attack directly non-linear
problems. As described in the previous chapters, neural networks have that
specific property.
Many constrained optimisation problems encountered in industrial appli-
cations are combinatorial problems. Underlying graph theory problems are
often NP-complete [Garey et al. 1979]: in other words, the number of possible
solutions undergoes combinatorial explosion, i.e., it grows exponentially with
the number of variables. It is then possible to use heuristics, which are ad-hoc
techniques. Although unable to find exact solutions, they are able to find good
solutions in a reasonable computational time, but with no guarantee on their
optimality.
8.2.1 Example
The above-described TSP is combinatorial and belongs to the family of NP-
complete problems [Reinelt 1994]. The number of potential solutions, i.e., of
possible tours, for a TSP with N cities, is N !. Thus, for the example given
Fig. 8.1, the number of potential solutions is greater than 10 159 . Obviously,
an exhaustive enumeration of all those possible solutions cannot possibly be
performed. Even an approach consisting in picking at random many potential
solutions and keeping the best one would not provide good results. In fact,
those solutions would represent a tiny part of the set of possible solutions.
Therefore, using more elaborate techniques for providing good solutions in a
reasonable search time is mandatory.
8.3 Classical Approaches to Combinatorial Problems
To solve the linear programs with integer variables, which are combinatorial
problems frequently encountered in applications, some heuristics have been
proposed, such as cutting planes methods, which add constraints to reduce
the convex envelop of the solutions [Schrijver 1986].
Branch-and-bound methods are exact methods, which try to enumerate, in
an educated way, the feasible solutions, in such a way that good solutions are
found rapidly [Prins 1994]. They split the solution space into subsets that are
smaller and smaller, most of them being eliminated after bounds calculation