In many applications, the solution of an optimization problem makes sense only if certain of the unknowns are integers. Integer linear programming problems have the general form
where is the set of n-dimensional
integer vectors. In mixed-integer linear programs, some components of x
are allowed to be real. We restrict ourselves to the pure integer case, bearing in mind
that the software can also handle mixed problems with little additional complication of
the underlying algorithm.
Integer programming problems, such as the fixed-charge network flow problem
and the famous traveling salesman problem, are often expressed in terms of binary
variables. The fixed-charge network problem modifies the minimum-cost network flow
paradigm by adding a term to the
cost, where the binary variable
is set to 1 if arc
carries a nonzero flow
; it is
set to zero otherwise.
In other words, there is a fixed overhead cost for using the arc at all. In the
traveling salesman problem, we need to find a tour of a number of cities that are
connected by directed arcs, so that each city is visited once and the time required to
complete the tour is minimized. One binary variable is assigned to each directed arc; a
variable is set to 1 if
city i immediately follows city j on the tour, and to zero otherwise.
Up To:
Down To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
