CPA Routine

Summary

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

Declaration

Function CPA(A: TMtx; b, c: TVec; AFinal: TMtx; x: TVec; Indexes: TVec; out SolutionType: TLPSolution; Minimize: boolean = true; Verbose: TStrings = nil): TSample;

Description

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

with decision variables being restricted to integer values.

See Also
SimplexLP

Example 1

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: TSample;
    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 "MtxVecCpp.h" //MtxVecCPP.cpp must be included in the project
    #include "Math387.hpp"
    #include "Optimization.hpp"
    void __fastcall Example;
    {
      Matrix A,Af;
      Vector b,c,x,indexes;
      TLPSolution sol;
      A->SetIt(2,2,false, OPENARRAY(TSample,(1,-1,2,4)));
      b->SetIt(OPENARRAY(TSample,(2,15)));
      c->SetIt(OPENARRAY(TSample,(1,-3)));
      // Find minimum using above system
      TSample f = CPA(A,b,c,,Af,x,indexes,sol,true,NULL);
      // f = -9.0
      // x1=0, x2=3
    }

    using Dew.Math;
    using Dew.Math.Units;

    namespace Dew.Examples
    {
      private void Example()
      {
        Matrix A = new Matrix(0,0);
        Matrix AFinal = new Matrix(0,0);
        Vector b = new Vector(0);
        Vector c = new Vector(0);
        Vector x = new Vector(0);
        Vector indexes = new Vector(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,AFinal,x,indexes, out sol, true,null);
        // f = -9.0
        // x1=0, x2=3
      }
    }