hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox Chapter Introduction

H — operations research

Scope of the Chapter

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

Background to the Problems

General linear programming (LP) problems (see Dantzig (1963)) are of the form:
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 Chapter E04.
IP problems may or may not have a solution, which may or may not be unique.
Consider for example the following problem:
minimize 3x1 + 2x2 subject to 4x1 + 2x25 2x25 0x1 - 0x22 and 0x1 0,x20.  
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 3x1+2x2, 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 x1+x2, 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
3x12  
were added to the above problem.
(c) There may be no feasible region, e.g., if an additional constraint
x1+x2 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
4x1+2x25,  x10,  x20,  
were deleted from the above problem.
Figure 1
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.
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 and nonlinear programming (NLP) problems using sequential convex QP approximations.
Functions have been introduced into this chapter to formally apply the technique to dense general QP problems and to sparse LP, QP or NLP problems. Scaling in the E04 Chapter Introduction describes the virtues of having a well-scaled problem. The imposition that a variable be integer makes this more difficult and some practical common sense might be required to make the problem tractable. If a variable is expected to have a large value at the minimum, say 100000 for instance, then in practical terms it might be better to forget the integer constraint and simply round off the final answer. To do otherwise forces a high level of computation accuracy on the underlying optimiser that might be impossible to achieve.
A special type of linear programming problem is the transportation problem in which there are p×q variables ykl which represent quantities of goods to be transported from each of p sources to each of q destinations.
The problem is to minimize
k=1pl=1qcklykl  
where ckl is the unit cost of transporting from source k to destination l. The constraints are:
l=1qykl=Ak availabilities k=1pykl=Bl requirements ykl0.  
Note that the availabilities must equal the requirements:
k= 1pAk=l= 1qBl=k= 1pl= 1qykl  
and if all the Ak and Bl are integers, then so are the optimal ykl.
The shortest path problem is that of finding a path of minimum length between two distinct vertices ns and ne through a network. Suppose the vertices in the network are labelled by the integers 1,2,,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), xij the amount of flow in arc i,j and dij the length of the arc i,j. The LP formulation of the problem is thus given as
minimize  dijxijsubject to ​Ax=b,  0x1, (1)
where
aij= + 1 if arc ​ j​ is directed away from vertex ​ i, -1 if arc ​ j​ is directed towards vertex ​ i, 0 otherwise  
and
bi= +1 for ​i=ns, -1 for ​i=ne, 0 otherwise.  
The above formulation only yields a meaningful solution if xij=0​ or ​1; that is, arci,j forms part of the shortest route only if xij=1. In fact since the optimal LP solution will (in theory) always yield xij=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. In the classical travelling salesman problem 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). Such IP problems could be solved directly by a mixed integer nonlinear programming solver; however, there are currently no functions in the Library that directly solve such IP problems. However, an acceptable solution to symmetric distance problems may be sought using the probabilistic optimization method known as simulated annealing for which a function is available. Asymmetric problems can be tackled by the introduction of shadow cities with zero distance between an original city and its shadow. Incomplete problems, where bidirectional travel between each pair of cities is not possible, can be tackled by attributing very large distances to unavailable journeys. For example, a salesperson might not mind backtracking through a previously visited city if this produced the shortest route. This problem is known as the practical travelling salesman problem.
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 functions in this chapter. The first of these uses reverse communication; the second direct communication (see Direct and Reverse Communication functions in Calling NAG Routines From MATLAB for a description of the difference between these two conventions).

Recommendations on Choice and Use of Available Functions

nag_mip_ilp_dense (h02bb) solves dense integer programming problems using a branch and bound method.
nag_mip_ilp_print (h02bv) prints the solution to an integer or a linear programming problem using specified names for rows and columns.
nag_mip_ilp_info (h02bz) supplies further information on the optimum solution obtained by nag_mip_ilp_dense (h02bb).
nag_mip_iqp_dense (h02cb) solves dense integer general quadratic programming problems.
nag_mip_iqp_dense_optstr (h02cd) supplies optional parameter values to nag_mip_iqp_dense (h02cb).
nag_mip_iqp_sparse (h02ce) solves sparse integer linear programming or quadratic programming problems.
nag_mip_iqp_sparse_optstr (h02cg) supplies optional parameter values to nag_mip_iqp_sparse (h02ce).
nag_mip_transportation (h03ab) 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.
nag_mip_shortestpath (h03ad) solves shortest path problems using Dijkstra's algorithm.
nag_mip_tsp_simann (h03bb) is a (symmetric) classical travelling salesman problem.
nag_mip_ilp_dense (h02bb) and nag_mip_transportation (h03ab) treat all matrices as dense and hence are not intended for large sparse problems. For solving large sparse LP problems, use nag_opt_qpconvex2_sparse_solve (e04nq) or nag_opt_nlp1_sparse_solve (e04ug).

Transportation Problem

nag_mip_transportation (h03ab) 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

nag_best_subset_given_size_revcomm (h05aa) selects the best n subsets of size p using a reverse communication branch and bound algorithm.
nag_best_subset_given_size (h05ab) selects the best n subsets of size p using a direct communication branch and bound algorithm.

Functionality Index

Feature selection, 
    best subset, 
        Given size, 
            direct communication nag_best_subset_given_size (h05ab)
            reverse communication nag_best_subset_given_size_revcomm (h05aa)
Integer programming problem (dense): 
    print solution with specified names nag_mip_ilp_print (h02bv)
    solve LP problem using branch and bound method nag_mip_ilp_dense (h02bb)
    solve nonlinear problem SQP nag_mip_sqp (h02da)
    solve QP problem using branch and bound method nag_mip_iqp_dense (h02cb)
    supply further information on the solution obtained from nag_mip_ilp_dense (h02bb) nag_mip_ilp_info (h02bz)
Integer programming problem (sparse): 
    solve LP or QP problem using branch and bound method nag_mip_iqp_sparse (h02ce)
Service functions, 
    optional parameter getting function for use with nag_mip_sqp (h02da) nag_mip_optget (h02zl)
    optional parameter setting function for use with  nag_mip_sqp (h02da) nag_mip_optset (h02zk)
Shortest path, through directed or undirected network nag_mip_shortestpath (h03ad)
Supply optional parameter values to nag_mip_iqp_dense (h02cb) nag_mip_iqp_dense_optstr (h02cd)
Supply optional parameter values to nag_mip_iqp_sparse (h02ce) nag_mip_iqp_sparse_optstr (h02cg)
Transportation problem nag_mip_transportation (h03ab)
Travelling Salesman Problem, simulated annealing nag_mip_tsp_simann (h03bb)

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

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015