function BranchAndBound(const A: TMtx; const b: TVec; const c: TVec; const AFinal: TMtx; const X: TVec; const Indexes: TVecInt; out SolutionType: TLPSolution; Minimize: Boolean; const Verbose: TStrings): Double;
Solve an all-integer linear program by branch and bound (Land and Doig).
| # | Name | Description |
|---|---|---|
| 1 | A | Constraint matrix of the A*x <= b relation |
| 2 | A.Rows = number of constraints (m), A.Cols = number of variables (n). | |
| 3 | b | Right-hand side vector of A*x <= b (length m) |
| 4 | any sign. | |
| 5 | c | Cost vector in f = c^T x (length n). |
| 6 | AFinal | Unused on return (sized to 0x0) |
| 7 | present for signature parity with [see | Dew.Math.Units.Optimization.CPA]. |
| 8 | X | Returns the integer optimum (length n). |
| 9 | Indexes | Unused on return (sized to 0) |
| 10 | present for signature parity with [see | Dew.Math.Units.Optimization.CPA]. |
| 11 | SolutionType | Returns the class of the solution. |
| 12 | Minimize | If true (the default) minimize f, otherwise maximize f. |
| 13 | Verbose | Optional log / TOptControl for interruption and iteration monitoring. |
Returns: Double
Solves the integer linear programming problem
min (max) f(x)=c^Tx subject to A x <= b, x >= 0, x in Z,
with all decision variables restricted to integer values. The components of b may have any sign. Branch and bound is robust on degenerate problems where the fractional cutting planes of Optimization.CPA stall; the search tree is finite, so the method always terminates.
Returns f = c^T x at the integer optimum, the integral point in X (length A.Cols) and the solution class in SolutionType:
LPFiniteSolution: a bounded integer optimum was found.
LPEmptyFeasableRegion: the integer feasible set is empty or the relaxation is unbounded; X is set to zero and NAN is returned.
An exception is raised if c.Length differs from A.Cols, if b.Length differs from A.Rows, or if the search-tree node limit is exceeded. The computation runs in the precision of A.
Reference: A. H. Land and A. G. Doig, "An automatic method of solving discrete programming problems", Econometrica 28 (1960), 497-520.
Optionally, you can also assign a TOptControl object to the Verbose parameter. This allows the optimization procedure to be interrupted from another thread and optionally also allows logging and iteration count monitoring.
Uses MtxExpr, MtxExprInt, Optimization, Math387;
procedure Example;
var A, AF: Matrix;
b, c, x: Vector;
indexes: VectorInt;
sol: TLPSolution;
f: double;
begin
A.SetIt(2,2,false,[1,1,
10,6]);
b.SetIt(false,[5,45]);
c.SetIt(false,[1,1]);
f := BranchAndBound(A,b,c,AF,x,indexes,sol,false,nil);
// f = 5, x = (3, 2)
end;