Integer Programming
From NEOS
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
| minimize | cTx |
| subject to | Ax = b |
| |
 ,
|
where Zn 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 complic ation 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 fijyij to the cost, where the binary variable yijis set to 1 if arc (i,j) 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 a re connected by directed arcs, so that each city is visited once and the time requ ired to complete the tour is minimized. One binary variable is assigned to each directe d arc; a variable xij is set to 1 if city i immediately follows city j on the tour, and to zero otherwise.
