View source for Discrete programming

<!--
d0331101.png
$#A+1 = 48 n = 0
$#C+1 = 48 : ~/encyclopedia/old_files/data/D033/D.0303110 Discrete programming
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A branch of mathematics the subject of which is the study and solution of extremal problems on finite sets. Let  $  M = \{ a _ {1} \dots a _ {n} \} $
and let  $  f $
be a numerical function defined on the elements of  $  M $. 
The task is to find an element  $  a _ {j} \in M $
on which the absolute minimum (or the absolute maximum) of  $  f $
on  $  M $
is obtained. Such problems are written down in an abbreviated form as follows:

$$ 
f( x) _ {x \in M }  \rightarrow  \textrm{ extr }
$$

$$ 
\left ( f( x) _ {x \in M }  \rightarrow  \min \  \textrm{ or }
\  f( x) _ {x \in M }  \rightarrow  \max \right ) .
$$

Discrete programming deals only with the non-trivial problems in this class of problems, which meet the following additional conditions.

1) The number  $  n = | M | $
must be sufficiently large for the problem not to be solvable by direct inspections of the values of  $  f ( a _ {i} ) $
manually or with the aid of an electronic computer. Thus, in the [[travelling salesman problem]] (which is a typical discrete programming problem), the number of possibilities to traverse  $  m $
points is

$$ 
( m - 1 ) !  \sim  c \sqrt {m } \left ( 
\frac{m - 1 }{e}
 \right ) ^ 
{m - 1 } .
$$

In the problems of minimization of Boolean functions (cf. [[Boolean functions, minimization of|Boolean functions, minimization of]]; [[Boolean functions, metric theory of|Boolean functions, metric theory of]])  $  | M | > 2 ^ {2  ^ {n} } $.

2) The problem must not be regular. A problem is said to be regular if: a) for each  $  a _ {i} \in M $
there is a non-empty neighbourhood  $  S ( a _ {i} , M ) $
and  $  | S ( a _ {i} , M ) | \ll  | M | $; 
b) a local extremum of  $  f $, 
i.e. a point  $  a _ {i} $
such that  $  f ( a _ {i} ) =  \mathop{\rm extr}  f( x) $, 
$  x \in S ( a _ {i} , M ) $, 
is defined by a simple algorithm; and c) a local extremum coincides with at least one global extremum.

Thus, discrete programming deals with problems involving, generally speaking, several local extrema. In typical cases the number of local extrema is very large. Thus, in problems of integer [[Linear programming|linear programming]] with Boolean variables, in which the objective function and the constraints depend on variables  $  x _ {1} \dots x _ {k} $, 
the number of elements in  $  M $
does not exceed  $  2  ^ {k} $, 
and the number of local extrema may be equal to  $  \textrm{ const }  2  ^ {k} / \sqrt k $[[#References|[2]]]. The degree of difficulty of solving discrete programming problems is determined by the presence of a large number of local extrema. At the time of writing (1988) there are no effective universal methods for solving discrete programming problems. Studies on the minimization of Boolean functions (which is a thoroughly studied model in discrete programming, cf. [[Algorithm, local|Algorithm, local]]) indicate that it is impossible to develop such methods. Sufficiently universal methods, such as branch-and-bound methods [[#References|[1]]] and their various modifications, are methods based on implicit enumeration. They are effectively employed in solving specialized discrete programming problems. However, there is a wide class of problems for which any implicit enumeration method is only little less complex than explicit enumeration methods. Another source of mathematical difficulties in discrete programming problems is that the set  $  M $
on which the extremum of  $  f $
is sought is often given in an implicit form. Thus, in problems of integer linear programming the set  $  M $
is defined as the collection of integer solutions of a system of linear inequalities. If  $  M $
is defined in this way or even in a more complex manner, not only the task of complete enumeration of  $  M $, 
but even of specifying a single element of  $  M $
becomes a non-trivial problem. As a result, the main results in discrete programming were obtained in solving and studying narrower classes of problems. These include the transportation problem (cf. [[Transport problem|Transport problem]]), the travelling salesman problem and the multi-salesman problem, integer linear programming, scheduling problems (cf. [[Scheduling theory|Scheduling theory]]), extremal problems on graphs (cf. [[Graph theory|Graph theory]]), and problems on the minimal representation of Boolean functions and functions of  $  k $-
valued logic, etc.

Another trend in the theory of discrete extremal problems is the development of approximation methods, which are usually employed in solving large-size practical problems. In principle, there is no difference between these methods and the corresponding search methods for the extrema of continuous functions and functionals. In discrete programming the algorithms employed are analogues of algorithms of local optimization, descent, random search, etc. For a review of approximation methods of problem solving by discrete programming see [[#References|[3]]].

The statistical approach to discrete programming problems is of both theoretical and of applied interest. Let a collection of problems  $  \{ Z \} $
be representable in the form  $  \{ Z \} = \cup _ {n=} 1  ^  \infty  \{ Z \} _ {n} $, 
where  $  | \{ Z \} _ {i} | > | \{ Z \} _ {j} | $
if  $  i> j $
and  $  | \{ Z \} _ {n} | \rightarrow \infty $
if  $  n \rightarrow \infty $. 
One says that the subset

$$ 
\{ Z ^ { \prime } \}  =  \cup _ {n = 1 } ^  \infty   \{ Z ^ { \prime } \} _ {n} ,\  \{ Z ^ { \prime } \} _ {n} \subset  \{ Z \} _ {n} ,
$$

contains almost-all problems  $  Z $
if

$$ 
\lim\limits _ {n \rightarrow \infty }  
\frac{| \{ Z ^ { \prime } \} _ {n} | }{| \{ Z \} | }
  =  1 .
$$

The following fact applies to various classes of discrete programming problems: There exists a collection  $  \{ Z ^ { \prime } \} $
of almost-all problems  $  \{ Z \} $
for which it is possible to find the extremum or a good approximation to it in the class of simple algorithms; this collection is often effectively described. This was first noted in solving the problems of synthesis of optimal control systems, e.g. in the minimization of Boolean functions in the class of disjunctive normal forms (see [[Boolean functions, normal forms of|Boolean functions, normal forms of]], and also [[#References|[4]]]). For instance, the problem of isolating the extremal conjunctions comprised in at least one minimal disjunctive normal form of a Boolean function  $  F ( x _ {1} \dots x _ {n} ) $
is unsolvable in the class of local algorithms if  $  k \cdot l < \textrm{ const } \cdot 2  ^ {n} $, 
where  $  k $
is the index of the local algorithm and  $  l $
is the size of the memory. At the same time the problem of isolating the elementary conjunctions forming part of at least one "almost-minimal" disjunctive normal form for almost-all Boolean functions is solvable in the class of local algorithms if  $  k= 2 $, 
$  l= 1 $[[#References|[5]]]. A similar considerable reduction of the labour involved in almost-all problems may be obtained for extremal problems on graphs, construction of optimal coverings, etc.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> A.A. Korbut, Yu.Yu. Finkel'shtein, "Discrete programming" , Moscow (1969) (In Russian) {{MR|0261958}} {{ZBL|0839.90116}} {{ZBL|0576.90069}} {{ZBL|0218.90034}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> V.K. Korobkov, "On certain integer-valued problems of linear programming" ''Probl. Kibernetiki'' , '''14''' (1965) pp. 297–299 (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> Yu.Yu. Finkel'shtein, "Approximate methods and applied problems in discrete programming" , Moscow (1976) (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow (1974) (In Russian) {{MR|}} {{ZBL|1185.68346}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> Yu.I. Zhuravlev, "Appraisals of the complexity of local algorithms for certain extremal properties on finite sets" ''Diskretn. Anal.'' , '''3''' (1964) pp. 41–77 (In Russian)</TD></TR></table>

====Comments====
Discrete programming, or "combinatorial optimizationcombinatorial optimization" , is a very active research area, which integrates and stimulates developments in discrete mathematics, [[Probability theory|probability theory]], [[Operations research|operations research]], and computer science. A number of benchmark references from the Western literature is given below.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> M. Gondran, M. Minoux, "Graphs and algorithms" , Wiley (1984) {{MR|0745802}} {{ZBL|0611.90096}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> E.L. Lawler, "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston (1976) {{MR|0439106}} {{ZBL|0413.90040}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> E.L. Lawler (ed.) J.K. Lenstra (ed.) A.H.G. Rinnooy Kan (ed.) D.B. Shmoys (ed.) , ''The traveling salesman problem: a guided tour of combinatorial optimization'' , Wiley (1985) {{MR|}} {{ZBL|0562.00014}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization. Algorithms and complexity" , Prentice-Hall (1982) {{MR|0663728}} {{ZBL|0503.90060}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> A. Schrijver, "Theory of linear and integer programming" , Wiley (1986) {{MR|0874114}} {{ZBL|0665.90063}} </TD></TR></table>