Combinatorial Optimization: An Introduction
In the end let us return to the beginning and consider the hypothetical Berlin airlift model of Chapter 1.2.3 for the sake of concreteness. As we have noted there the linear programming solution to the formulation is truly an approximation to the problem
- PDF / 3,767,248 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 20 Downloads / 232 Views
Sempre avanti ... Italian saying. In the end let us return to the beginning and consider the hypothetical Berlin airlift model of Chapter 1.2.3 for the sake of concreteness. As we have noted there the linear programming solution to the formulation is truly an approximation to the problem that the decision-maker faces: pHots are, of course, "indivisible" and because of that he would like answers in terms of the natural numbers 0,1,2,3, ... rather than in rationals or reals. So we have to require that some or all of the variables of the model must be integer-valued. The integrality requirement on some or all of the variables of a linear program introduces a combinatorial aspect into the problem that makes the resulting optimization problem, in general, far more difficult than the linear programming problem. In linear programming we have the entire apparatus of duality which makes it possible to verify or falsify the asserted optimality of some feasible solution. Given a feasible solution to the Berlin airlift model in integers, there is no corresponding theory to conclude optimality or nonoptimality of a particular solution. To prove optimality we will have to resort either to some sort of enumeration or we will have to embed the original problem into a more "constrained" problem that permits us to apply the duality theory of linear programming. One way in which a combinatorial optimization problem arises is thus in the form of a so-called mixed-integer linear program (MIP)
max{cx + dy: Ax + Dy
~
b, x
~
0 and integer, y
~
O} ,
where A is any m x n matrix of reals, D is an m x p matrix of reals, b is a column vector with m real components and c and d are real row vectors of length n and p, respectively. If n = 0 then we have simply a linear program. If p = 0 then we have a pure integer program . The variables x that must be integer-valued are referred to as integer variables of the problem, the variables y as the real variables or, sometimes, as the ftow variables of the problem. Frequently, there are explicit upper bounds on either the integer or real variables or both given. Indeed in many applications the integer variables M. Padberg, Linear Optimization and Extensions © Springer-Verlag Berlin Heidelberg 1999
388
10. Combinatorial Optimization: An Introduction
model yes/no decisions, Le. they are required to ass urne only the values of zero or one. In this case the problem (MIP) is referred to as a mixed zero-one or, simply, as a zero-one linear program depending on p > 0 or p = o. A different, more abstract way in which combinatorial problems arise go es as follows: given some finite ground set E = {I, ... , g} of 9 distinct elements let F be a finite family of not necessarily distinct subsets F ~ E that satisfy certain well-defined conditions. Let Ce for all e E E be the "cost" of element e and define CF = LeEF Ce to be the cost of F E F. We want to find F* E F such that the cost of F* is minimal, Le. we want to solve the combinatorial optimization problem min
{L
Ce :
F
E
F} .
(10.1)
eEF
To mo
Data Loading...
