Optimization.CPA Function

Gomory's cutting plane algorithm for solving the integer programming problem.

Pascal

function CPA(const A: TMtx; const b: TVec; const c: TVec; const AFinal: TMtx; const X: TVec; const Indexes: TVecInt; out SolutionType: TLPSolution; Minimize: boolean = true; const Verbose: TStrings = nil): double;

File

Optimization

Description

Implements the Gomory's Cutting Plane Algorithm (CPA) for solwing the following linear programming problem

with decision variables being restricted to integer values.

Optionally, you can also assign 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.

See Also

SimplexLP

Example

Minimize the following linear programming problem:

f(x)=x1-3x2 (x1,x2 integers)

x1-x2=2

2x1+4x2=15

which translates to:

uses MtxExpr, Math387, Optimization; procedure Example; var A,AFinal: Matrix; b,c,x,ind: Vector; st: TLPSolution; fmin: double; begin A.SetIt(2,2,false,[1,-1,2,4]); b.SetIt(false,[2,15]); c.SetIt(false,[1,-3]); fmin := CPA(A,b,c,AFinal,x,ind,st,true,nil); // fmin = -9.0 // x1=0, x2=3 end;

#include "MtxExpr.hpp" #include "Math387.hpp" #include "Optimization.hpp" void __fastcall Example; { sMatrix A,Af; sVector b,c,x,indexes; TLPSolution sol; A.SetIt(2,2,false, OPENARRAY(double,(1,-1,2,4))); b.SetIt(OPENARRAY(double,(2,15))); c.SetIt(OPENARRAY(double,(1,-3))); // Find minimum using above system double f = CPA(A,b,c,,Af,x,indexes,sol,true,NULL); // f = -9.0 // x1=0, x2=3 }

Optimization, Functions, Example, See Also

What do you think about this topic? Send feedback!