bintprog - Solve binary integer programming problems

Equation

Solves binary integer programming problems of the form

f, b, and beq are vectors, A and Aeq are matrices, and the solution x is required to be a binary integer vector—that is, its entries can only take on the values 0 or 1.

Syntax

x = bintprog(f) x = bintprog(f,A,b) x = bintprog(f,A,b,Aeq,beq) x = bintprog(f,A,b,Aeq,beq,x0) x = bintprog(f,A,b,Aeq,Beq,x0,options) x = bintprog(problem) [x,fval] = bintprog(...) [x,fval,exitflag] = bintprog(...) [x,fval,exitflag,output] = bintprog(...)

Description

x = bintprog(f) solves the binary integer programming problem

x = bintprog(f,A,b) solves the binary integer programming problem

x = bintprog(f,A,b,Aeq,beq) solves the preceding problem with the additional equality constraint.

Aeq·x = beq.

x = bintprog(f,A,b,Aeq,beq,x0) sets the starting point for the algorithm to x0. If x0 is not in the feasible region, bintprog uses the default initial point.

x = bintprog(f,A,b,Aeq,Beq,x0,options) minimizes with the default optimization options replaced by values in the structure options, which you can create using the function optimset.

x = bintprog(problem) finds the minimum for problem, where problem is a structure described in Input Arguments.

Create the structure problem by exporting a problem from Optimization Tool, as described in Exporting to the MATLAB Workspace.

[x,fval] = bintprog(...) returns fval, the value of the objective function at x.

[x,fval,exitflag] = bintprog(...) returns exitflag that describes the exit condition of bintprog. See Output Arguments.

[x,fval,exitflag,output] = bintprog(...) returns a structure output that contains information about the optimization. See Output Arguments.

Input Arguments

The following table lists the input arguments for bintprog. Function Arguments contains general descriptions of input arguments for optimization functions.

`f`	Vector containing the coefficients of the linear objective function.
`A`	Matrix containing the coefficients of the linear inequality constraints A·x≤ b.
`b`	Vector corresponding to the right-hand side of the linear inequality constraints.
`Aeq`	Matrix containing the coefficients of the linear equality constraints Aeq·x = beq.
`beq`	Vector containing the constants of the linear equality constraints.
`x0`	Initial point for the algorithm.
`options`	Options structure containing options for the algorithm.
`problem`	`f`	Linear objective function vector `f`
	`Aineq`	Matrix for linear inequality constraints
	`bineq`	Vector for linear inequality constraints
	`Aeq`	Matrix for linear equality constraints
	`beq`	Vector for linear equality constraints
	`x0`	Initial point for `x`
	`solver`	`'bintprog'`
	`options`	Options structure created with `optimset`

Output Arguments

Function Arguments contains general descriptions of arguments returned by bintprog. This section provides specific details for the arguments exitflag and output:

`exitflag`	Integer identifying the reason the algorithm terminated. The following lists the values of `exitflag` and the corresponding reasons the algorithm terminated.
	`1`	Function converged to a solution `x`.
	`0`	Number of iterations exceeded `options.MaxIter`.
	`-2`	The problem is infeasible.
	`-4`	Number of searched nodes exceeded `options.MaxNodes`.
	`-5`	Search time exceeded `options.MaxTime`.
	`-6`	Number of iterations the LP-solver performed at a node to solve the LP-relaxation problem exceeded `options.MaxRLP`.
`output`	Structure containing information about the optimization. The fields of the structure are
	`iterations`	Number of iterations taken
	`nodes`	Number of nodes searched
	`time`	Execution time of the algorithm
	`algorithm`	Optimization algorithm used
	`branchStrategy`	Strategy used to select branch variable—see Options
	`nodeSearchStrategy`	Strategy used to select next node in search tree—see Options
	`message`	Exit message

Options

Optimization options used by bintprog. You can use optimset to set or change the values of these fields in the options structure options. See Optimization Options for detailed information.

`BranchStrategy`	Strategy the algorithm uses to select the branch variable in the search tree—see Branching. The choices are `'mininfeas'` — Choose the variable with the minimum integer infeasibility (the variable whose value is closest to `0` or `1`, but not equal to `0` or `1`). `'maxinfeas'` — Choose the variable with the maximum integer infeasibility (the variable whose value is closest to `0.5` (default)).
`Diagnostics`	Display diagnostic information about the function. The choices are `'on'` or the default, `'off'`.
`Display`	Level of display. `'off'` displays no output `'iter'` displays output at each iteration `'final'` (default) displays just the final output
`MaxIter`	Maximum number of iterations allowed (a positive integer). The default is `100000*numberOfVariables`
`MaxNodes`	Maximum number of solutions, or nodes, the function searches (a positive integer). The default is `1000*numberOfVariables`
`MaxRLPIter`	Maximum number of iterations the LP-solver performs to solve the LP-relaxation problem at each node (a positive integer). The default is `100*numberOfVariables`
`MaxTime`	Maximum amount of CPU time in seconds the function runs (a positive scalar). The default is `7200`.
`NodeDisplayInterval`	Node display interval (a positive integer). Gives the number of nodes to search between reporting to the iterative display. The default is `20`.
`NodeSearchStrategy`	Strategy the algorithm uses to select the next node to search in the search tree—see Branching. The choices are: `'df'` — Depth-first search strategy. At each node in the search tree, if there is a child node one level down in the tree that has not already been explored, the algorithm chooses one such child to search. Otherwise, the algorithm moves to the node one level up in the tree and chooses a child node one level down from that node. `'bn'` — Best-node search strategy, which chooses the node with lowest bound on the objective function (the default).
`TolFun`	Termination tolerance on the function value (a positive scalar). The default is `1.0e-3`.
`TolXInteger`	Tolerance within which the value of a variable is considered to be integral (a positive scalar). The default is `1.0e-8`.
`TolRLPFun`	Termination tolerance on the function value of a linear programming relaxation problem (a positive scalar). The default is `1.0e-6`.

Algorithm

bintprog uses a linear programming (LP)-based branch-and-bound algorithm to solve binary integer programming problems. The algorithm searches for an optimal solution to the binary integer programming problem by solving a series of LP-relaxation problems, in which the binary integer requirement on the variables is replaced by the weaker constraint 0 ≤ x ≤ 1. The algorithm

Searches for a binary integer feasible solution
Updates the best binary integer feasible point found so far as the search tree grows
Verifies that no better integer feasible solution is possible by solving a series of linear programming problems

For more information, see bintprog Algorithm

Example

To minimize the function

f(x) = –9x₁ – 5x₂ – 6x₃ – 4x₄,

subject to the constraints

where x₁, x₂, x₃, and x₄ are binary integers, enter the following commands:

f = [-9; -5; -6; -4]; 
A = [6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1];
b = [9; 1; 0; 0];
x = bintprog(f,A,b) 
Optimization terminated.

x =
     1
     1
     0
     0

References

[1] Wolsey, Laurence A., Integer Programming, John Wiley & Sons, 1998.

[2] Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.

[3] Hillier, Frederick S. and Lieberman Gerald J., Introduction to Operations Research, McGraw-Hill, 2001.