|On this page…|
Binary integer programming is the problem of finding a binary vector x that minimizes a linear function fTx subject to linear constraints:
such that A·x ≤ b, Aeq·x = beq, x binary.
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
The following sections describe the branch-and-bound method in greater detail.
The algorithm creates a search tree by repeatedly adding constraints to the problem, that is, "branching." At a branching step, the algorithm chooses a variable xj whose current value is not an integer and adds the constraint xj = 0 to form one branch and the constraint xj = 1 to form the other branch. This process can be represented by a binary tree, in which the nodes represent the added constraints. The following picture illustrates a complete binary tree for a problem that has three variables, x1, x2, and x3. Note that, in general, the order of the variables going down the levels in the tree is not the usual order of their subscripts
At each node, the algorithm solves an LP-relaxation problem using the constraints at that node and decides whether to branch or to move to another node depending on the outcome. There are three possibilities:
If the LP-relaxation problem at the current node is infeasible or its optimal value is greater than that of the best integer point, the algorithm removes the node from the tree, after which it does not search any branches below that node. The algorithm then moves to a new node according to the method you specify in NodeSearchStrategy option.
If the algorithm finds a new feasible integer point with lower objective value than that of the best integer point, it updates the current best integer point and moves to the next node.
If the LP-relaxation problem is optimal but not integer and the optimal objective value of the LP relaxation problem is less than the best integer point, the algorithm branches according to the method you specify in the BranchStrategy option.
See Options for a description of the NodeSearchStrategy and BranchStrategy options.
The solution to the LP-relaxation problem provides a lower bound for the binary integer programming problem. If the solution to the LP-relaxation problem is already a binary integer vector, it provides an upper bound for the binary integer programming problem.
As the search tree grows more nodes, the algorithm updates the lower and upper bounds on the objective function, using the bounds obtained in the bounding step. The bound on the objective value serves as the threshold to cut off unnecessary branches.
The algorithm for bintprog could potentially search all 2n binary integer vectors, where n is the number of variables. As a complete search might take a very long time, you can limit the search using the following options
MaxNodes — Maximum number of nodes the algorithm searches
MaxRLPIter — Maximum number of iterations the LP-solver performs at any node
MaxTime — Maximum amount of time in seconds the algorithm runs
See Options for more information.