double CPA(TMtx *A, TVec *b, TVec *c, TMtx *AFinal, TVec *X, TVecInt *Indexes, TLPSolution &SolutionType, bool Minimize = true, tStrings *Verbose = null);
Gomory's cutting plane algorithm for integer linear programming.
| # | Name | Type | Description |
|---|---|---|---|
| 1 | A | TMtx * | |
| 2 | b | TVec * | |
| 3 | c | TVec * | |
| 4 | AFinal | TMtx * | |
| 5 | X | TVec * | |
| 6 | Indexes | TVecInt * | |
| 7 | SolutionType | TLPSolution & | |
| 8 | Minimize = true | bool | |
| 9 | Verbose = null | tStrings * |
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 Optimization::SimplexLP; for b of any sign use 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. 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 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.