Introduction

Summary

A discrete-optimization problem is a problem of maximizing a real-valued objective function c on a finite set of feasible solutions S. Often the set S naturally arises as a subset of 2^E (the set of all subsets of E), for some finite ground set E, in which case we have a combinatorial-optimization problem. Of course, there is no problem because we can just enumerate all feasible solutions but we seek to do better. Usually, the feasible solutions are described in some concise manner, rather than being explicitly listed. The challenge is to develop algorithms that are provably or practically better than enumerating all feasible solutions.

Applications of discrete-optimization problems arise in industry (e.g., manufacturing and distribution, telecommunication-network design and routing, airline crew scheduling) and in applied sciences (e.g., statistics, physics, and chemistry).

Besides the applications, discrete optimization has aspects that connect it with other areas of mathematics (e.g., algebra, analysis and continuous optimization, geometry, logic, numerical analysis, topology, and, of course, other subdisciplines of discrete mathematics such as graph theory, matroid theory, and enumerative combinatorics) as well as computer science. Thus research in discrete optimization is driven by mathematics as well as by applications.

It is almost always the case that the set of feasible solutions S is delivered to us descriptively rather than by an explicit list. For example, S might be the set of spanning trees of a connected graph.