H Chapter Introduction : NAG Library CL Interface, Mark 30

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 Chapter E04.

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 function document for h02buc.

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.

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. Section 2.6 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 \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 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 Section 7 in How to Use the NAG Library for a description of the difference between these two conventions).

3 Recommendations on Choice and Use of Available Functions

h02bkc solves large-scale mixed integer linear programming problems using a branch and bound method.

3.1 Integer Programming

The IP function in Chapter H provides a range of optional facilities: these offer the possibility of fine control over many of the algorithmic parameters and the means of adjusting the level and nature of the printed results. The MPSX reading function also offers some optional facilities.

Control of these optional facilities is exercised by a structure of type Nag_H02_Opt, the members of the structure being optional input or output arguments to the function. After declaring the structure variable, which is named options in this manual, you must initialize the structure by passing its address in a call to the utility function h02xxc. Selected members of the structure may then be set to your required values and the address of the structure passed to the NAG function. Any member which has not been set by you will indicate to the function that the default value should be used for this argument. A more detailed description of this process is given below in Section 3.1.4.

Examples of arguments which may be altered from their default value are options.feas_tol and options.int_tol (these control the accuracy to which the constraints are satisfied in the B&B sub-problems and the accuracy of the final objective function value, respectively), and options.max_iter (which limits the number of iterations the algorithm will perform at each sub-problem). Certain members of options supply further details concerning the final results, for example on exit from the IP solver the member pointers options.state and options.lambda give the status of the constraints and the final values of the Lagrange multipliers respectively. Another use of the options structure is to allow additional information read in by the MPSX reader (such as the MPSX row and column names) to be communicated to the IP solver for use in its printout.

3.1.1 Control of Printed Output

Results from the IP solution process are printed by default on the stdout (standard output) stream. These include the results after each node of the B&B search tree and the final results at termination of the search process. The amount of detail printed out may be increased or decreased by setting the optional parameter print_level, i.e., the structure member options.print_level. This member is an enum type, Nag_PrintType, and an example value is Nag_Soln which when assigned to options.print_level will cause the IP function to print only the final result; all intermediate results printout is suppressed.

If the results printout is not in the desired form then it may be switched off, by setting

options.print_level = Nag_NoPrint

, or alternatively you can supply your own function to printout or make use of both the intermediate and final results. Such a function would be assigned to the pointer to function member options.print_fun; the user-defined function would then be called in preference to the NAG print function.

In addition to the results, the values of the arguments to the optimization function are printed out when the function is entered; the Boolean member options.list may be set to Nag_FALSE if this listing is not required.

Printing may be output to a named file rather than to stdout by providing the name of the file in the options character array member outfile. Error messages will still appear on stderr, if

fail.print = Nag_TRUE

or the fail argument is supplied as NAG_DEFAULT (see Section 7 in the Introduction to the NAG Library CL Interface for details of error handling within the library). The level of output provided by the MPSX reading function may also be controlled. In this case, control is provided by the optional parameter output_level.

3.1.2 Memory Management

The options structure contains a number of pointers for the input of data and the output of results. The NAG functions will manage the allocation of memory to these pointers; when all calls to these functions have been completed then a utility function h02xzc can be called by your program to free the NAG allocated memory which is no longer required.

If the calling function is part of a larger program then this utility function allows you to conserve memory by freeing the NAG allocated memory before the options structure goes out of scope. h02xzc can free all NAG allocated memory in a single call, but it may also be used selectively. In this case the memory assigned to certain pointers may be freed leaving the remaining memory still available; pointers to this memory and the results it contains may then be passed to other functions in your program without passing the structure and all its associated memory.

Although the NAG C Library functions will manage all memory allocation and deallocation, it may occasionally be necessary for you to allocate memory to the options structure from within the calling program before entering the optimization function.

An example of this is where you store information in a file from an optimization run and at a later date wish to use that information to solve a similar optimization problem or the same one under slightly changed conditions. The pointer options.state, for example, would need to be allocated memory by you before the status of the constraints could be assigned from the values in the file.

If you assign memory to a pointer within the options structure then the deallocation of this memory must also be performed by you; the utility function h02xzc will only free memory allocated by NAG C Library optimization functions. When user allocated memory is freed using the standard C library function free() then the pointer should be set to NULL immediately afterwards; this will avoid possible confusion in the NAG memory management system if a NAG function is subsequently entered.

3.1.3 Reading Optional Parameter Values From a File

Optional parameter values may be placed in a file by you and the function h02xyc used to read the file and assign the values to the options structure. This utility function permits optional parameter values to be supplied in any order and altered without recompilation of the program. The values read are also checked before assignment to ensure they are in the correct range for the specified option. Pointers within the options structure cannot be assigned to using h02xyc.

3.1.4 Method of Setting Optional Parameters

The method of using and setting the optional parameters is:

step 1	Declare a structure of type Nag_H02_Opt.
step 2	Initialize the structure using h02xxc.
step 3	Assign values to the structure.
step 4	Pass the address of the structure to the optimization function.
step 5	Call h02xzc to free any memory allocated by the optimization function.

If after step 4, you wish to re-enter the optimization function, then step 3 can be returned to directly, i.e., step 5 need only be executed when all calls to the optimization function have been made.

At step 3, values can be assigned directly and/or by means of the option file reading function h02xyc. If values are only assigned from the options file then step 2 need not be performed as h02xyc will automatically call h02xxc if the structure has not been initialized.

3.2 Transportation Problem

h03abc 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.

3.3 Feature Selection – Best Subset Problem

h05aac selects the best