Double CPA(TMtx A, TVec b, TVec c, TMtx AFinal, TVec X, TVecInt Indexes, ref TLPSolution SolutionType, Boolean Minimize, TStrings Verbose)
Gomory's cutting plane algorithm for integer linear programming.
| # | Name | Type | Description |
|---|---|---|---|
| 1 | A | TMtx | source TMtx |
| 2 | b | TVec | source TVec |
| 3 | c | TVec | source TVec |
| 4 | AFinal | TMtx | source TMtx |
| 5 | X | TVec | source TVec |
| 6 | Indexes | TVecInt | source TVecInt |
| 7 | SolutionType | TLPSolution (ref) | |
| 8 | Minimize | Boolean | |
| 9 | Verbose | TStrings |
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 right-hand side vector b must be nonnegative, as for Dew.Math.Units.Optimization.SimplexLP; for b of any sign use Dew.Math.Units.Optimization.BranchAndBound.
Returns f = c^T x at the integer optimum, the integral point in X (length A.Cols), the indices of the basic variables in Indexes, the final tableau in AFinal and the solution class in SolutionType:
LPFiniteSolution: a bounded integer optimum was found. The returned objective is never better than the continuous optimum.
LPUnboundedObjectiveFunction: the continuous relaxation is unbounded; X is set to zero and -INF (minimize) or +INF (maximize) is returned.
LPEmptyFeasableRegion: a generated cut admits no dual-simplex pivot, which the pure fractional cutting plane method cannot recover from on some degenerate problems (Schrijver, Theory of Linear and Integer Programming, 1986, section 23.8); X is set to zero and NAN is returned. Dew.Math.Units.Optimization.BranchAndBound solves such problems.
An exception is raised if c.Length differs from A.Cols, if b.Length differs from A.Rows, or if an internal iteration limit is exceeded. The computation runs in the precision of A.
Reference: R. E. Gomory, "An algorithm for integer solutions to linear programs", in Recent Advances in Mathematical Programming (R. L. Graves and P. Wolfe, eds.), McGraw-Hill, 1963, pp. 269-302.
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,
2,4});
b.SetIt(new double[] {2,15});
c.SetIt(new double[] {1,-3});
double f = Optimization.CPA(A,b,c,Af,x,indexes, out sol, true, null);
// f = -9, x = (0, 3)
}
}