Documentation Center

  • Trial Software
  • Product Updates

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 options, which you can create using the function optimoptions.

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

Create the problem structure by exporting a problem from Optimization app, as described in Exporting Your Work.

[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·xb.

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 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 created with optimoptions

Output Arguments

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

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

Iterative display

bintprog-specific iterative display:

Best lower bound on obj

Objective function value of LP relaxation problem that gives the best current lower bound on the final objective function value.

Explored nodes

Cumulative number of explored nodes.

Obj of best integer point

Objective function value of the best integer point found so far. This is an upper bound for the final objective function value.

Obj of LP relaxation

Objective function value of the linear programming (LP) relaxation problem.

Relative gap between bounds

where

  • b is the objective function value of the best integer point.

  • a is the best lower bound on the objective function value.

Unexplored nodes

Number of nodes that have been set up but not yet explored.

Options

Optimization options used by bintprog. Use optimoptions to set or change options. See Optimization Options Reference 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' or 'none' displays no output.

  • 'iter' displays output at each iteration, and gives the default exit message.

  • 'iter-detailed' displays output at each iteration, and gives the technical exit message.

  • 'final' (default) displays just the final output, and gives the default exit message.

  • 'final-detailed' displays just the final output, and gives the technical exit message.

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.

Examples

To minimize the function

f(x) = –9x1 – 5x2 – 6x3 – 4x4,

subject to the constraints

where x1, x2, x3, and x4 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

More About

expand all

Tips

  • intlinprog solves more problems than bintprog, and has better performance. To update your existing bintprog code to use intlinprog, make the following changes:

    • Set intcon to 1:numVars, where numVars is the number of variables in your problem.

    • Set lb to zeros(numVars,1).

    • Set ub to ones(numVars,1).

    • Update any relevant options. Use optimoptions to create options for intlinprog.

    • Change your call to bintprog as follows:

      [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options)
      % Change your call to:
      [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,options)

Algorithms

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

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.

See Also

| |

Was this topic helpful?