Double BranchAndBound(TMtx A, TVec b, TVec c, TMtx AFinal, TVec X, TVecInt Indexes, ref TLPSolution SolutionType, Boolean Minimize, TStrings Verbose)
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 / Dew.Math.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 Dew.Math.Units.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 Dew.Math.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.
using Dew.Math;
using Dew.Math.Units;
namespace Dew.Examples
{
private void Example()
{
Matrix A = new Matrix(0,0);
Matrix Af = new Matrix(0,0);
Vector b = new Vector(0);
Vector c = new Vector(0);
Vector x = new Vector(0);
VectorInt indexes = new VectorInt(0);
TLPSolution sol;
A.SetIt(2,2,false, new double[] {1,1,
10,6});
b.SetIt(new double[] {5,45});
c.SetIt(new double[] {1,1});
double f = Optimization.BranchAndBound(A,b,c,Af,x,indexes, out sol, false, null);
// f = 5, x = (3, 2)
}
}