double BranchAndBound(TMtx *A, TVec *b, TVec *c, TMtx *AFinal, TVec *X, TVecInt *Indexes, TLPSolution &SolutionType, bool Minimize = true, tStrings *Verbose = null);
Solve an all-integer linear program by branch and bound (Land and Doig).
| # | Name | Type | Description |
|---|---|---|---|
| 1 | A | TMtx * | Constraint matrix of the A*x <= b relation; A.Rows = number of constraints (m), A.Cols = number of variables (n). |
| 2 | b | TVec * | Right-hand side vector of A*x <= b (length m); any sign. |
| 3 | c | TVec * | Cost vector in f = c^T x (length n). |
| 4 | AFinal | TMtx * | Unused on return (sized to 0x0); present for signature parity with Optimization::CPA. |
| 5 | X | TVec * | Returns the integer optimum (length n). |
| 6 | Indexes | TVecInt * | Unused on return (sized to 0); present for signature parity with Optimization::CPA. |
| 7 | SolutionType | TLPSolution & | Returns the class of the solution. |
| 8 | Minimize = true | bool | If true (the default) minimize f, otherwise maximize f. |
| 9 | Verbose = null | tStrings * | Optional log / TOptControl for interruption and iteration monitoring. |
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.
#include "MtxExpr.h"
#include "MtxExprInt.h"
#include "Optimization.h"
#include "Units.Optimization.h"
using namespace Dew;
using namespace Dew::Math;
using namespace Dew::Math::Units::Optimization;
void Example()
{
Matrix A(0,0);
Matrix Af(0,0);
Vector b(0);
Vector c(0);
Vector x(0);
VectorInt indexes(0);
TLPSolution sol;
A.SetIt(2,2,false, DewArray<double>{1,1,
10,6});
b.SetIt(DewArray<double>{5,45});
c.SetIt(DewArray<double>{1,1});
double f = BranchAndBound(A,b,c,Af,x,indexes, sol, false, nullptr);
// f = 5, x = (3, 2)
}