#include <LGCIGenerator.h>

Public Member Functions
	LGCIGenerator (ProblemPtr p, SolutionPtr s, EnvPtr env, LPEnginePtr lpengine)

	LGCIGenerator (RelaxationPtr rel, ConstSolutionPtr sol, EnvPtr env, LPEnginePtr lpengine)

void	initialize ()

void	initStats ()

bool	hasCover (ConstraintConstIterator it)

bool	hasGubCover (ConstraintConstIterator it, ConstConstraintVectorPtr gublist)

bool	coverSetGeneratorGNS (ConstConstraintPtr cons, CoverSetPtr cover)

bool	coverSetGenGNSModified (ConstConstraintPtr cons)

void	varCoeff (ConstConstraintPtr cons, CoverSetPtr cover)

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)

double	lift (const ConstCoverSetPtr obj, const ConstCoverSetPtr inequality, const CoverSetConstIterator variable, double &rhs, double &initialb, bool uplift)

void	initCoverIneq (const ConstCoverSetPtr cover, CoverSetPtr coverineq)

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

bool	liftSet (CoverSetPtr obj, CoverSetPtr constraintset, const ConstCoverSetPtr varset, CoverSetPtr inequality, double &ub, double &initialb, bool liftup)

void	generateCuts (ConstConstraintPtr cons, ConstConstraintVectorPtr gublist)

CutPtr	generateCut (const ConstCoverSetPtr inequality, double ub)

bool	GNS (const ConstConstraintPtr cons, ConstConstraintVectorPtr gublist)

void	addCut (CutPtr cut)

bool	addCut (CoverSetPtr cov, double rhs, UInt cuttype, CutFail &failtype)

bool	checkExists (CoverSetPtr inequality, double rhs)

double	liftingProbsolver ()

double	violation (CutPtr cut)

void	nonzeroVars (const ConstLinearFunctionPtr lf, CoverSetPtr nonzerovars, CoverSetPtr zerovars)

void	sortNonIncreasing (CoverSetPtr nonzeros)

void	cBar (const ConstCoverSetPtr cover, CoverSetPtr cbar, const ConstConstraintPtr cons)

void	generateGubMaps (ConstConstraintVectorPtr gublist, std::vector< CoverSetPtr > gubcoverlist, std::vector< CoverSetPtr > guborigcoeffs)

void	nonOverlap (std::vector< CoverSetPtr > *gubcoverlist)

void	initGubCons (const ConstCoverSetPtr cone, std::vector< CoverSetPtr > gubcoverlist, std::vector< CoverSetPtr > gubcons)

void	liftSet (CoverSetPtr obj, std::vector< CoverSetPtr > origgubs, CoverSetPtr consknap, std::vector< CoverSetPtr > gubcons, const ConstCoverSetPtr varset, CoverSetPtr coverineq, double &rhs, double &initialknap, double *initialgub, bool liftup)

double	lift (CoverSetPtr obj, std::vector< CoverSetPtr > origgubs, CoverSetPtr consknap, std::vector< CoverSetPtr > gubcons, const CoverSetConstIterator variable, double &rhs, double &initialbknap, double *initialgub, bool liftup)

ConstProbStructPtr	getProbStruct () const

ConstKnapsackListPtr	getKnapsackList () const

ConstLGCIGenStatsPtr	getStats () const

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

void	addCons (CoverSetPtr obj, CoverSetPtr consknap, double bknap, std::vector< CoverSetPtr > gubcons, double bgubs, OrigLiftVarsPtr varmap, ProblemPtr liftprob)

VariablePtr	addVar (VariablePtr var, OrigLiftVarsPtr varmap, ProblemPtr liftprob)

double	roundHeur (ProblemPtr prob)

Detailed Description

LGCIGenerator class generates lifted GUB cover inequalities from a given problem and a solution. It generates the list of knapsack inequalities suitable for cut generation. It checks if the considered knapsack constraint has at least one cover. If not then it checks another knapsack inequality. It generates an overlapping GUB set that covers knapsack variables. It by using a simple elimination rule, i.e., take out duplicates, obtains a non-overlapping GUB set.

Member Function Documentation

◆ addCons()

void LGCIGenerator::addCons	(	CoverSetPtr	obj,
		CoverSetPtr	consknap,
		double	bknap,
		std::vector< CoverSetPtr > *	gubcons,
		double *	bgubs,
		OrigLiftVarsPtr	varmap,
		ProblemPtr	liftprob
	)

This is used to call OsiClpInterface. This function prepares the problem data for lifting problem solver. Updates rhs of lifting problem and rhs of cover inequality.

◆ addVar()

VariablePtr LGCIGenerator::addVar	(	VariablePtr	var,
		OrigLiftVarsPtr	varmap,
		ProblemPtr	liftprob
	)

Checks if the variable is already added. If added it returns a pointer to the variable. Otherwise, it creates a new variable and sends its pointer.

◆ cBar()

void LGCIGenerator::cBar	(	const ConstCoverSetPtr	cover,
		CoverSetPtr	cbar,
		const ConstConstraintPtr	cons
	)

This function generates set N-C, the variables outdide of cover set.

◆ checkExists()

bool LGCIGenerator::checkExists	(	CoverSetPtr	inequality,
		double	rhs
	)

TODO: Create a new index for variables in the knapsack only. Do not consider all variables for coefficients.

◆ coverPartitionGNS()

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

Assumption: cover is an minimal cover. cone, ctwo, fset, and fbar are empty sets.

◆ coverSetGeneratorGNS()

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

Assumption: An empty cover is given. Initial cover will be generated from scratch.

◆ liftingGNS()

bool LGCIGenerator::liftingGNS	(	const ConstCoverSetPtr	cone,
		const ConstCoverSetPtr	ctwo,
		const ConstCoverSetPtr	fset,
		const ConstCoverSetPtr	rset,
		CoverSetPtr	ineq,
		const ConstConstraintPtr	cons,
		ConstConstraintVectorPtr	gublist,
		double &	rhs
	)

Lifting strategy of GNS for LGCI lifting. Different from Knapsack cover genereator. Generates Gu, Nemhauser, Savelsbergh LGCI generation algorithm.

Lifting strategy of GNS. Assumptions: Sets C1, C2, F and R are given as described in paper of GNS (not empty). For lifting sequence, we do not consider GNS for GUBwise lifting. The reason is we do not solve lifting problem exactly. The GUBwise lifting decreases computational effort to solve consequent lifting problems. We simply use GNS lifting sequence as in given order order in their set. This order can be changed later. Inequality is given as empty. Vectors are not sorted or anything else.

◆ liftSet() [1/2]

bool Minotaur::LGCIGenerator::liftSet	(	CoverSetPtr	obj,
		CoverSetPtr	constraintset,
		const ConstCoverSetPtr	varset,
		CoverSetPtr	inequality,
		double &	ub,
		double &	initialb,
		bool	liftup
	)

This lifts the variables in a given set in the given order

◆ liftSet() [2/2]

void LGCIGenerator::liftSet	(	CoverSetPtr	obj,
		std::vector< CoverSetPtr > *	origgubs,
		CoverSetPtr	consknap,
		std::vector< CoverSetPtr > *	gubcons,
		const ConstCoverSetPtr	varset,
		CoverSetPtr	coverineq,
		double &	rhs,
		double &	initialbknap,
		double *	initialbgub,
		bool	liftup
	)

Assumptions: Following data elements should be suitable for lifitng problem construction. Objective, lifting problem constraints, variable set to be lifted, inequality to be lifted, rhs of inequality, rhs of lifting problem constraints. Under these assumptions, this function determine the coefficient of lifted variable, adds the new variable to inequality being lifted, lifting problem objective function, and lifting problem constraints. obj, consknap, gubcons, rhs, initialbknap, initialbgub are changed at the end. varset and liftup does not change.

◆ minimalCover()

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

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

◆ sortNonIncreasing()

void LGCIGenerator::sortNonIncreasing ( CoverSetPtr nonzeros )

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

◆ sumCoeffs()

double LGCIGenerator::sumCoeffs ( CoverSetPtr cover )

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

◆ varCoeff()

void LGCIGenerator::varCoeff	(	ConstConstraintPtr	cons,
		CoverSetPtr	cover
	)

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/LGCIGenerator.h
/home/amahajan/tmp/minotaur-test/src/base/LGCIGenerator.cpp

Public Member Functions