Basic Concepts
Consider the following general combinatorial optimization problem. Let \(\mathbb{F}\) be a family of subsets of a finite set \(E\) and let \(w: E \rightarrow \mathbb{R}\) be a real-valued weight function defined on the elements of \(E\). The objective of the combinatorial optimization problem is to find \(F^* \in \mathbb{F}\) such that
\[w(F^*) = \mbox{min}_{F \in \mathbb{F}} w(F)\]
where \(w(F) := \sum_{e \in \mathbb{F}} w(e)\).
To translate the combinatorial optimization problem into an optimization problem in \(\mathbb{R}^E\), we can represent each \(F \in \mathbb{F}\) by its incidence vector. Let \(\chi_e^F = 1\) if \(e \in F\) and \(\chi_e^F = 0\) otherwise. Then, if we let \(S = \{\chi^F: F \in \mathbb{F}\} \subseteq \{0,1\}^E\) be the set of incidence vectors of the sets in \(\mathbb{F}\), the corresponding optimization problem is
\[\mbox{min}\{w^T x : x \in S\}.\]
Examples
Traveling Salesman Problem
Perhaps the most famous combinatorial optimization problem is the Traveling Salesman Problem (TSP). Given a complete graph on \(n\) vertices and a weight function defined on the edges, the objective of the TSP is to construct a tour (a circuit that passes through each vertex) of minimum total weight. The TSP is an example of a hard combinatorial optimization problem; the decision version of the problem is \(\mathcal{NP}\)-complete. Below is an integer programming formulation of the TSP.
Integer Programming Formulation
The TSP can be formulated as an integer linear programming problem. Let \(N\) be the set of vertices (cities) and let \(c_{ij}\) be the weight of the edge connecting vertex \(i\) and vertex \(j\). Let decision variable \(x_{ij}\) take the value 1 if the tour includes the edge connecting \(i\) and \(j\) and the value 0 otherwise.
Minimize \( \sum_{i \in N} \sum_{j \in N} c_{ij} x_{ij}\)
subject to: must enter each vertex exactly once
\(\sum_{i \in N} x_{ij} = 1, \quad \forall j \in N\)
subject to: must exit each vertex exactly once
\(\sum_{j \in N} x_{ij} = 1, \quad \forall i\in N\)
subject to: subtour elimination constraints
\(\sum_{i, j \in S} x_{ij} \leq |S| – 1, \quad \forall S \subset N\)
subject to: integrality constraints
\(x_{ij}\) integer
Cutting Stock Problem
The Cutting Stock Problem is an \(\mathcal{NP}\)-complete optimization problem that arises in many applications in industry. The classic one-dimensional cutting stock problem is to determine how to cut rolls of paper of fixed-width into customer orders for smaller widths so as to minimize waste. The cutting stock problem can be formulated as an integer linear programming problem and solved using column generation. The Cutting Stock Problem case study presents a small example, provides an integer linear programming formulation, and discusses the delayed column generation approach. The Wikipedia entry lists a number of examples and provides some references. VPSolver is a vector packing solver based on an arc-flow formulation with graph compression; it generates models that can be solved using general-purpose mixed-integer programming solvers. In two-dimensional cutting stock problems, rectangular (or more general) shapes are to be cut from a larger sheet. There are both guillotine and non-guillotine versions.
Packing Problems
Packing Problems can be viewed as complementary to cutting problems in that the objective is to fill a larger space with specified smaller shapes in the most economical (profitable) way. There are geometric packing problems in one dimension, two dimensions and even three dimensions, such as those that arise in filling trucks or shipping containers. The size measure is not always length or width; it may be weight, for example.
Minimum Spanning Tree
Another well-known combinatorial optimization problem is the Minimum Spanning Tree (MST) problem. Given a connected, undirected graph, a spanning tree of the graph is a subgraph that is a tree and connects all the vertices. Given a weight assigned to each edge, a minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.
The MST problem is an example of an easy combinatorial optimization problem. Two common algorithms, Prim’s Algorithm and Kruskal’s Algorithm, are greedy algorithms that run in polynomial time; the decision version of the MST problem is in \(\mathcal{P}\). MSTs have direct applications in the design of networks of all types (computer, telecommunications, transportation, water supply and electricity) and arise as subproblems in the solution of optimization problems (e.g., TSP).
References
- Ahuja, R. K., Magnanti, T. L., and J. B. Orlin. 1993. Network Flows. Prentice-Hall, Inc., Upper Saddle River, NJ.
- Bertsekas, D. P. 1998. Network Optimization: Continuous and Discrete Models. Athena Scientific, Nashua, NH.
- Lawler, E. 2001. Combinatorial Optimization: Networks and Matroids. Dover Publications, Inc., Mineola, NY.
- Murty, K. G. 2006. Network Programming, Internet Edition.. First published in 1992 by Prentice-Hall, Inc., Upper Saddle River, NJ.
- Nemhauser, G. L. and Wolsey, L. A. 1988. Integer and Combinatorial Optimization. John Wiley & Sons, New York.
- Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Inc., Mineola, NY.
- Rockafellar, R. T. 1998. Network Flows and Monotropic Optimization. Athena Scientific, Nashua, NH.
- Optimization Online Combinatorial Optimization area