Package org.drip.optimization.cuttingplane

Class ChvatalGomoryCut

java.lang.Object

org.drip.optimization.canonical.ILPConstraint

org.drip.optimization.cuttingplane.ChvatalGomoryCut

All Implemented Interfaces:

LinearConstraint

Direct Known Subclasses:

BurdetJohnsonCut, LetchfordLodiCut, StrengthenedBurdetJohnsonCut, StrengthenedChvatalGomoryCut

public class ChvatalGomoryCut
extends ILPConstraint

ChvatalGomoryCut implements the ILP Chvatal-Gomory Cut. The References are:

• Burdet, C. A., and E. L. Johnson (1977): A Sub-additive Approach to Solve Linear Integer Programs Annals of Discrete Mathematics 1 117-143
• Chvatal, V. (1973): Edmonds Polytopes in a Hierarchy of Combinatorial Problems Discrete Mathematics 4 (4) 305-337
• Gomory, R. E. (1958): Outline of an Algorithm for Integer Solutions to Linear Programs Bulletin of the American Mathematical Society 64 (5) 275-278
• Kelley, J. E. (1960): The Cutting Plane Method for Solving Convex Problems Journal for the Society of the Industrial and Applied Mathematics 8 (4) 703-712
• Letchford, A. N. and A. Lodi (2002): Strengthening Chvatal-Gomory Cuts and Gomory Fractional Cuts Operations Research Letters 30 (2) 74-82

• Module = Computational Core Module
• Library = Numerical Optimizer Library
• Project = Necessary, Sufficient, and Regularity Checks for Gradient Descent and LP/MILP/MINLP Schemes
• Package = Polyhedral Cutting Plane Generation Schemes

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
ChvatalGomoryCut(int[][] aGrid, int[] bArray, double[] lambdaArray)	ChvatalGomoryCut Constructor

Method Summary

Modifier and Type	Method	Description
double[]	adjustedCoefficientArray()	Generate the Adjusted Coefficient Array
double[]	lambdaArray()	Retrieve the Lambda Array
double[]	unadjustedCoefficientArray()	Generate the Unadjusted Coefficient Array
boolean	verify(int[] variateArray)	Verify if the Variate Array satisfies the Constraint

Methods inherited from class org.drip.optimization.canonical.ILPConstraint

aGrid, bArray, burdetJohnsonCut, chvatalGomoryCut, constraintCount, dimension, strengthenedBurdetJohnsonCut, strengthenedChvatalGomoryCut, validate

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

ChvatalGomoryCut

public ChvatalGomoryCut(int[][] aGrid,
int[] bArray,
double[] lambdaArray)
                 throws java.lang.Exception

ChvatalGomoryCut Constructor

Parameters:

aGrid - "A" Constraint Grid

bArray - "b" Constraint Array

lambdaArray - The Lambda Array

Throws:

java.lang.Exception - Thrown if the Inputs are Invalid

Method Details

lambdaArray

public double[] lambdaArray()

Retrieve the Lambda Array

Returns:

The Lambda Array

unadjustedCoefficientArray

public double[] unadjustedCoefficientArray()

Generate the Unadjusted Coefficient Array

Returns:

The Unadjusted Coefficient Array

adjustedCoefficientArray

public double[] adjustedCoefficientArray()

Generate the Adjusted Coefficient Array

Returns:

The Adjusted Coefficient Array

verify

public boolean verify(int[] variateArray)
               throws java.lang.Exception

Verify if the Variate Array satisfies the Constraint

Overrides:

verify in class ILPConstraint

Parameters:

variateArray - The Input Variate Array

Returns:

TRUE - The Variate Array satisfies the Constraint

Throws:

java.lang.Exception - Thrown if the Verification cannot be done