Discrete programming

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, 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 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 $[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) indicate that it is impossible to develop such methods. Sufficiently universal methods, such as branch-and-bound methods [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), the travelling salesman problem and the multi-salesman problem, integer linear programming, scheduling problems (cf. Scheduling theory), extremal problems on graphs (cf. 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 [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, and also [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 $[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

[1]	A.A. Korbut, Yu.Yu. Finkel'shtein, "Discrete programming" , Moscow (1969) (In Russian) MR0261958 Zbl 0839.90116 Zbl 0576.90069 Zbl 0218.90034
[2]	V.K. Korobkov, "On certain integer-valued problems of linear programming" Probl. Kibernetiki , 14 (1965) pp. 297–299 (In Russian)
[3]	Yu.Yu. Finkel'shtein, "Approximate methods and applied problems in discrete programming" , Moscow (1976) (In Russian)
[4]	, Discrete mathematics and mathematical problems in cybernetics , 1 , Moscow (1974) (In Russian) Zbl 1185.68346
[5]	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)

Comments

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

References

[a1]	M. Gondran, M. Minoux, "Graphs and algorithms" , Wiley (1984) MR0745802 Zbl 0611.90096
[a2]	E.L. Lawler, "Combinatorial optimization: networks and matroids" , Holt, Rinehart & Winston (1976) MR0439106 Zbl 0413.90040
[a3]	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) Zbl 0562.00014
[a4]	C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization. Algorithms and complexity" , Prentice-Hall (1982) MR0663728 Zbl 0503.90060
[a5]	A. Schrijver, "Theory of linear and integer programming" , Wiley (1986) MR0874114 Zbl 0665.90063