This chapter provides methods to solve certain integer programming, transportation and shortest path problems. Additionally ‘best subset’ methods are included.

Syntax

C#
public static class H

Visual Basic
Public NotInheritable Class H

Visual C++
public ref class H abstract sealed

F#
[<AbstractClassAttribute>] [<SealedAttribute>] type H = class end

Background to the Problems

General linear programming (LP) problems (see Dantzig (1963)) are of the form:

find $x = {(x_{1}, x_{2}, \dots, x_{n})}^{T}$ to maximize $F (x) = \sum_{j = 1}^{n} c_{j} x_{j}$
subject to linear constraints which may have the forms:
$\begin{array}{l} \sum_{j = 1}^{n} a_{i j} x_{j} = b_{i}, & i = 1, 2, \dots, m_{1} & (equality) \\ \sum_{j = 1}^{n} a_{i j} x_{j} \leq b_{i}, & i = m_{1} + 1, \dots, m_{2} & (inequality) \\ \sum_{j = 1}^{n} a_{i j} x_{j} \geq b_{i}, & i = m_{2} + 1, \dots, m & (inequality) \\ x_{j} \geq l_{j}, & j = 1, 2, \dots, n & (simple bound) \\ x_{j} \leq u_{j}, & j = 1, 2, \dots, n & (simple bound) \end{array}$

This chapter deals with integer programming (IP) problems in which some or all the elements of the solution vector

x

are further constrained to be integers. For general LP problems where

x

takes only real (i.e., noninteger) values, refer to E04 class.

IP problems may or may not have a solution, which may or may not be unique.

Consider for example the following problem:

\begin{array}{l} minimize & 3 x_{1} & + & 2 x_{2} \\ subject to & 4 x_{1} & + & 2 x_{2} \geq 5 \\ 2 x_{2} \leq 5 \\ x_{1} & - & x_{2} \leq 2 \\ and & x_{1} & \geq & 0, x_{2} \geq 0 . \end{array}

The hatched area in Figure 1 is the feasible region, the region where all the constraints are satisfied, and the points within it which have integer coordinates are circled. The lines of hatching are in fact contours of decreasing values of the objective function

3 x_{1} + 2 x_{2}

, and it is clear from Figure 1 that the optimum IP solution is at the point

(1, 1)

. For this problem the solution is unique.

However, there are other possible situations.

(a)

There may be more than one solution; e.g., if the objective function in the above problem were changed to

x_{1} + x_{2}

, both

(1, 1)

and

(2, 0)

would be IP solutions.

(b)

The feasible region may contain no points with integer coordinates, e.g., if an additional constraint

3 x_{1} \leq 2

were added to the above problem.

(c)

There may be no feasible region, e.g., if an additional constraint

x_{1} + x_{2} \leq 1

were added to the above problem.

(d)

The objective function may have no finite minimum within the feasible region; this means that the feasible region is unbounded in the direction of decreasing values of the objective function, e.g., if the constraints

4 x_{1} + 2 x_{2} \geq 5, x_{1} \geq 0, x_{2} \geq 0,

were deleted from the above problem.

Figure 1

Algorithms for IP problems are usually based on algorithms for general LP problems, together with some procedure for constructing additional constraints which exclude noninteger solutions (see Beale (1977)).

The Branch and Bound (B&B) method is a well-known and widely used technique for solving IP problems (see Beale (1977) or Mitra (1973)). It involves subdividing the optimum solution to the original LP problem into two mutually exclusive sub-problems by branching an integer variable that currently has a fractional optimal value. Each sub-problem can now be solved as an LP problem, using the objective function of the original problem. The process of branching continues until a solution for one of the sub-problems is feasible with respect to the integer problem. In order to prove the optimality of this solution, the rest of the sub-problems in the B&B tree must also be solved. Naturally, if a better integer feasible solution is found for any sub-problem, it should replace the one at hand.

A common method for specifying IP and LP problems in general is the use of the MPSX file format (see IBM (1971)). A full description of this file format is provided in the method document for (H02BUF not in this release).

The efficiency in computations is enhanced by discarding inferior sub-problems. These are problems in the B&B search tree whose LP solutions are lower than (in the case of maximization) the best integer solution at hand.

The B&B method may also be applied to convex quadratic programming (QP) problems. Methods have been introduced into this chapter to formally apply the technique to dense general QP problems and to sparse LP or QP problems.

A special type of linear programming problem is the transportation problem in which there are

p \times q

variables

y_{k l}

which represent quantities of goods to be transported from each of

p

sources to each of

q

destinations.

The problem is to minimize

\sum_{k = 1}^{p} \sum_{l = 1}^{q} c_{k l} y_{k l}

where

c_{k l}

is the unit cost of transporting from source

k

to destination

l

. The constraints are:

\begin{array}{l} \sum_{l = 1}^{q} y_{k l} = A_{k} & (availabilities) \\ \sum_{k = 1}^{p} y_{k l} = B_{l} & (requirements) \\ y_{k l} \geq 0 . \end{array}

Note that the availabilities must equal the requirements:

\sum_{k = 1}^{p} A_{k} = \sum_{l = 1}^{q} B_{l} = \sum_{k = 1}^{p} \sum_{l = 1}^{q} y_{k l}

and if all the

A_{k}

and

B_{l}

are integers, then so are the optimal

y_{k l}

The shortest path problem is that of finding a path of minimum length between two distinct vertices

n_{s}

and

n_{e}

through a network. Suppose the vertices in the network are labelled by the integers

1, 2, \dots, n

. Let

(i, j)

denote an ordered pair of vertices in the network (where

i

is the origin vertex and

j

the destination vertex of the arc),

x_{i j}

the amount of flow in arc

(i, j)

and

d_{i j}

the length of the arc

(i, j)

. The LP formulation of the problem is thus given as

minimize \sum \sum d_{i j} x_{i j} subject to ​ A x = b, 0 \leq x \leq 1,

(1)

where

a_{i j} = \{\begin{cases} + 1 & if arc ​ j ​ is directed away from vertex ​ i, \\ - 1 & if arc ​ j ​ is directed towards vertex ​ i, \\ 0 & otherwise \end{cases}

and

b_{i} = \{\begin{cases} + 1 & for ​ i = n_{s}, \\ - 1 & for ​ i = n_{e}, \\ 0 & otherwise. \end{cases}

The above formulation only yields a meaningful solution if

x_{i j} = 0 ​ or ​ 1

; that is,

arc (i, j)

forms part of the shortest route only if

x_{i j} = 1

. In fact since the optimal LP solution will (in theory) always yield

x_{i j} = 0 ​ or ​ 1

, (1) can also be solved as an IP problem. Note that the problem may also be solved directly (and more efficiently) using a variant of Dijkstra's algorithm (see Ahuja et al. (1993)).

The travelling salesman problem is that of finding a minimum distance route round a given set of cities. The salesperson must visit each city only once before returning to his or her city of origin. It can be formulated as an IP problem in a number of ways. One such formulation is described in Williams (1993). There are currently no methods in the Library for solving such problems.

The best $n$ subsets problem assumes a scoring mechanism and a set of

m

features. The problem is one of choosing the best

n

subsets of size

p

. It is addressed by two methods in this chapter. The first of these uses reverse communication; the second direct communication.

Recommendations on Choice and Use of Available Methods

h02bb	solves dense integer programming problems using a branch and bound method.
(H02BFF not in this release)	solves dense integer or linear programming problems defined by a MPSX data file.
(H02BUF not in this release)	converts an MPSX data file defining an integer or a linear programming problem to the form required by e04mf or h02bb.
(H02BVF not in this release)	prints the solution to an integer or a linear programming problem using specified names for rows and columns.
(H02BZF not in this release)	supplies further information on the optimum solution obtained by h02bb.
h02cb	solves dense integer general quadratic programming problems.
(H02CCF not in this release)	reads optional parameter values for h02cb from external file.
(H02CDF not in this release)	supplies optional parameter values to h02cb.
h02ce	solves sparse integer linear programming or quadratic programming problems.
(H02CFF not in this release)	reads optional parameter values for h02ce from external file.
(H02CGF not in this release)	supplies optional parameter values to h02ce.
(H03ABF not in this release)	solves transportation problems. It uses integer arithmetic throughout and so produces exact results. On a few machines, however, there is a risk of integer overflow without warning, so the integer values in the data should be kept as small as possible by dividing out any common factors from the coefficients of the constraint or objective functions.
(H03ADF not in this release)	solves shortest path problems using Dijkstra's algorithm.

h02bb (H02BFF not in this release) (H03ABF not in this release) treat all matrices as dense and hence are not intended for large sparse problems. For solving large sparse LP problems, use e04nq or e04ug.

Transportation Problem

(H03ABF not in this release) solves transportation problems. It uses integer arithmetic throughout and so produces exact results. On a few machines, however, there is a risk of integer overflow without warning, so the integer values in the data should be kept as small as possible by dividing out any common factors from the coefficients of the constraint or objective functions.

Feature Selection – Best Subset Problem

(H05AAF not in this release) selects the best

n

subsets of size

p

using a reverse communication branch and bound algorithm.

(H05ABF not in this release) selects the best

n

subsets of size

p

using a direct communication branch and bound algorithm.

References

Ahuja R K, Magnanti T L and Orlin J B (1993) Network Flows: Theory, Algorithms and Applications Prentice–Hall

Beale E M (1977) Integer programming The State of the Art in Numerical Analysis (ed D A H Jacobs) Academic Press

Dantzig G B (1963) Linear Programming and Extensions Princeton University Press

IBM (1971) MPSX – Mathematical programming system Program Number 5734 XM4 IBM Trade Corporation, New York

Mitra G (1973) Investigation of some branch and bound strategies for the solution of mixed integer linear programs Math. Programming 4 155–170

Williams H P (1993) Model Building in Mathematical Programming (3rd Edition) Wiley

Inheritance Hierarchy

System..::..Object
NagLibrary..::..H

Syntax

Background to the Problems

Recommendations on Choice and Use of Available Methods

Transportation Problem

Feature Selection – Best Subset Problem

References

Inheritance Hierarchy

See Also