#include <CoverCutGenerator.h>

Public Member Functions
	CoverCutGenerator (ProblemPtr p, SolutionPtr s, EnvPtr env)

	CoverCutGenerator (RelaxationPtr rel, ConstSolutionPtr sol, EnvPtr env)

bool	initialize (RelaxationPtr p, ConstSolutionPtr s, EnvPtr env)

void	generateKnapList ()

bool	hasCover (ConstraintIterator it)

bool	GUB (ConstraintIterator itcons)

void	nonzeroVars (LinearFunctionPtr lf, CoverSetPtr nonzerovars, CoverSetPtr zerovars)

void	sortNonIncreasing (CoverSetPtr nonzeros)

void	sortReducedCosts (CoverSetPtr &vars)

bool	coverSetGeneratorGNS (ConstConstraintPtr cons, CoverSetPtr cover)

CoverSetPtr	coverSetGenGNSModified (ConstConstraintPtr cons)

CoverSetPtr	coverSetGeneratorDefault (ConstConstraintPtr cons)

CoverSetPtr	varCoeff (LinearFunctionPtr lf)

void	variableCoeffPair (CoverSetPtr cover, LinearFunctionPtr lf)

double	sumCoeffs (CoverSetPtr cover)

void	minimalCover (CoverSetPtr cover, ConstConstraintPtr cons)

void	generateAllCuts ()

void	coverPartitionGNS (const ConstConstraintPtr cons, const ConstCoverSetPtr cover, CoverSetPtr cone, CoverSetPtr ctwo, CoverSetPtr fset, CoverSetPtr rset)

void	cBar (const ConstCoverSetPtr coverSetPtr, CoverSetPtr cBar, const ConstConstraintPtr constraint)

double	lift (const ConstCoverSetPtr obj, const ConstCoverSetPtr constraint, const CoverSetConstIterator variable, double &rhs, double &inititalb, bool uplift)

void	simple (const ConstCoverSetPtr cover, const ConstCoverSetPtr cbar, const ConstConstraintPtr cons)

void	allCTwo (const ConstCoverSetPtr cover, const ConstCoverSetPtr cone, const ConstCoverSetPtr cbar, const ConstConstraintPtr cons)

void	initCoverIneq (const ConstCoverSetPtr coverset, CoverSetPtr coverineq)

bool	liftingGNS (const ConstCoverSetPtr cone, const ConstCoverSetPtr ctwo, const ConstCoverSetPtr fset, const ConstCoverSetPtr rset, CoverSetPtr constraint, const ConstConstraintPtr cons, double &ub)

void	liftSetF (CoverSetPtr obj, CoverSetPtr consknap, const ConstCoverSetPtr setf, CoverSetPtr coverineq, double &ub, double &initialb, const bool liftup)

void	liftSet (CoverSetPtr obj, CoverSetPtr consknap, const ConstCoverSetPtr varset, CoverSetPtr constraint, double &ub, double &initialb, bool liftup)

bool	GNS (const ConstConstraintPtr cons)

CutPtr	generateCut (const ConstCoverSetPtr constraint, const double ub)

void	addCut (CutPtr cut)

bool	checkExists (CoverSetPtr cov, double rhs)

void	generateCuts (ConstConstraintPtr constraint)

void	extendedCover (CoverSetPtr cover, ConstConstraintPtr cons)

UInt	binaryKnapsackSolver (size_t n, double b, double const c, double const a, double &z, int *x)

double	violation (CutPtr cut)

ConstProblemPtr	getProblem () const

ConstKnapsackListPtr	getKnapsackList () const

ConstSolutionPtr	getSolution () const

CutVector	getCutList () const

DoubleVector	getViolList () const

UInt	getNumCons () const

ConstCovCutGenStatsPtr	getStats () const

void	initStats ()

bool	addCut (CoverSetPtr cov, double rhs, UInt cuttype)

CutVector	getViolatedCutList () const

bool	checkIntegral (RelaxationPtr p, ConstSolutionPtr s)

void	printIneq (const ConstCoverSetPtr cov, double rhs, PrintType type, string message)

void	printLiftProb (const ConstCoverSetPtr obj, const ConstCoverSetPtr consknap, const CoverSetConstIterator variable, double rhs, double initialb, bool uplift, double b, double gamma, double alpha)

Detailed Description

The CoverCutGenerator class generates a set of minimal covers for each knapsack constraint. First, the knapsack list is created. Second, Cover cuts for a chosen minimal cover for a corresponding knapsack inequality is created the inequalites are added to a cut list.

Member Function Documentation

◆ coverSetGeneratorDefault()

CoverSetPtr CoverCutGenerator::coverSetGeneratorDefault ( ConstConstraintPtr cons )

This is the default cover set generator. It simply adds the variables to the set until the sum > b. It orders the variables in order of their coefficients in nonincreasing order. By this way, the cover will probably be minimal cover.

◆ coverSetGeneratorGNS()

bool CoverCutGenerator::coverSetGeneratorGNS	(	ConstConstraintPtr	cons,
		CoverSetPtr	cover
	)

Generates a cover set from a vector of variables and their coefficients in the knapsack constraint. It uses Gu, Nemhauser, Savelsbergh approach.

Assumption the cover set is empty at the beginning. Initial cpver will be generated from scratch.

◆ minimalCover()

void CoverCutGenerator::minimalCover	(	CoverSetPtr	cover,
		ConstConstraintPtr	cons
	)

Drops some of the variables and obtains a minimal cover form a given cover.

◆ sortNonIncreasing()

void CoverCutGenerator::sortNonIncreasing ( CoverSetPtr nonzeros )

We sort in nonincreasing order the variables according to their values in fractional solution.

◆ sumCoeffs()

double CoverCutGenerator::sumCoeffs ( CoverSetPtr cover )

Calculates the sum of coefficients of a given vector of variable-coefficient pairs

◆ varCoeff()

CoverSetPtr CoverCutGenerator::varCoeff ( LinearFunctionPtr lf )

This generates the variable-coefficient pair vector from a given linear function.

◆ variableCoeffPair()

void Minotaur::CoverCutGenerator::variableCoeffPair	(	CoverSetPtr	cover,
		LinearFunctionPtr	lf
	)

Constructs the variable-value pair vector from a given vector and a linear function that inclued coefficients.

The documentation for this class was generated from the following files:

/home/amahajan/tmp/minotaur-test/src/base/CoverCutGenerator.h
/home/amahajan/tmp/minotaur-test/src/base/CoverCutGenerator.cpp

Public Member Functions