Learn more about Optimization Toolbox

Binary Integer Programming

On this page…
Definition bintprog Algorithm

Definition

Binary integer programming is the problem of finding a binary vector x that minimizes a linear function f^Tx subject to linear constraints:

such that A·x ≤ b, Aeq·x = beq, x binary.

Back to Top

bintprog 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

The following sections describe the branch-and-bound method in greater detail.

Branching

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 x_j whose current value is not an integer and adds the constraint x_j = 0 to form one branch and the constraint x_j = 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, x₁, x₂, and x₃. Note that, in general, the order of the variables going down the levels in the tree is not the usual order of their subscripts

Deciding Whether to Branch

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.

Bounds

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.

Limits for the Algorithm

The algorithm for bintprog could potentially search all 2ⁿ 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.

Back to Top

Quadratic Programming Examples

Binary Integer Programming Example

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS