×

Connections between nonlinear programming and discrete optimization. (English) Zbl 0926.90081

Du, Ding-Zhu (ed.) et al., Handbook of combinatorial optimization. Vol. 1. Boston: Kluwer Academic Publishers. 149-188 (1998).
Although this is not an exhaustive survey of all connections between discrete optimization and nonlinear programming many interesting results are discussed. At first a general result on the equivalence between minimizing a function on a set and the problem of minimizing a penalized function on a larger set is given. This result is then used to reformulate integer programs as concave programs or as linear complementarity problems. Further the problem of establishing conditions under which a function achieves its minimum on the vertices of a polyhedron is discussed. In the next section it is proved that piecewise concave functions achieve their minimum on a set of points that is often finite. Then location problems are discussed and a generalization of bilinear programming problems are considered. Extension and relaxion of a function from a discrete set to a larger continuous set are discussed together with the opposite approach of discretizing a function defined on a polyhedron. Finally, some connections between global optimality conditions for continuous and discrete problems are given.
For the entire collection see [Zbl 0903.90001].

MSC:

90C27 Combinatorial optimization
90C30 Nonlinear programming
90C10 Integer programming

Keywords:

survey
PDFBibTeX XMLCite