Loading...
Searching...
No Matches
CglKnapsackCover.hpp
Go to the documentation of this file.
// $Id$
// Copyright (C) 2000, International Business Machines
// Corporation and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
#ifndef CglKnapsackCover_H
#define CglKnapsackCover_H
#include <string>
#include "CglCutGenerator.hpp"
#include "CglTreeInfo.hpp"
class CglKnapsackCover : public CglCutGenerator {
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
public:
void setTestedRowIndices(int num, const int* ind);
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
CglKnapsackCover ();
CglKnapsackCover (
const CglKnapsackCover &);
virtual CglCutGenerator * clone() const;
CglKnapsackCover &
operator=(
const CglKnapsackCover& rhs);
virtual
~CglKnapsackCover ();
virtual std::string generateCpp( FILE * fp);
virtual void refreshSolver(OsiSolverInterface * solver);
inline void setMaxInKnapsack(int value)
{ if (value>0) maxInKnapsack_ = value;}
inline int getMaxInKnapsack() const
{return maxInKnapsack_;}
inline void switchOffExpensive()
{ expensiveCuts_=false;}
inline void switchOnExpensive()
{ expensiveCuts_=true;}
private:
// Private member methods
int deriveAKnapsack(
const OsiSolverInterface & si,
OsiCuts & cs,
CoinPackedVector & krow,
bool treatAsLRow,
double & b,
int * complement,
double * xstar,
int rowIndex,
int numberElements,
const int * index,
const double * element);
int deriveAKnapsack(
const OsiSolverInterface & si,
OsiCuts & cs,
CoinPackedVector & krow,
double & b,
int * complement,
double * xstar,
int rowIndex,
const CoinPackedVectorBase & matrixRow);
int findExactMostViolatedMinCover(
int nCols,
int row,
CoinPackedVector & krow,
double b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder);
int findLPMostViolatedMinCover(
int nCols,
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder);
int findGreedyCover(
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder
);
int liftCoverCut(
double & b,
int nRowElem,
CoinPackedVector & cover,
CoinPackedVector & remainder,
CoinPackedVector & cut );
int liftAndUncomplementAndAdd(
double rowub,
CoinPackedVector & krow,
double & b,
int * complement,
int row,
CoinPackedVector & cover,
CoinPackedVector & remainder,
OsiCuts & cs );
void seqLiftAndUncomplementAndAdd(
int nCols,
double * xstar,
int * complement,
int row,
int nRowElem,
double & b,
CoinPackedVector & cover, // need not be violated
CoinPackedVector & remainder,
OsiCuts & cs );
void liftUpDownAndUncomplementAndAdd(
int nCols,
double * xstar,
int * complement,
int row,
int nRowElem,
double & b,
// the following 3 packed vectors partition the krow:
CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
// and form cover with the vars atOne
CoinPackedVector & atOne, // vars have soln value of 1 in lp relaxation
// and together with fracCover form minimal (?) cover.
CoinPackedVector & remainder,
OsiCuts & cs );
int findPseudoJohnAndEllisCover (
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder);
int findJohnAndEllisCover (
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & fracCover,
CoinPackedVector & atOnes,
CoinPackedVector & remainder);
int exactSolveKnapsack(
int n,
double c,
double const *pp,
double const *ww,
double & z,
int * x);
int gubifyCut(CoinPackedVector & cut);
public:
int createCliques( OsiSolverInterface & si,
int minimumSize=2, int maximumSize=100, bool extendCliques=false);
private:
void deleteCliques();
// Private member data
double epsilon_;
double epsilon2_;
double onetol_;
int maxInKnapsack_;
int numRowsToCheck_;
int* rowsToCheck_;
bool expensiveCuts_;
const OsiSolverInterface * solver_;
int whichRow_;
int * complement_;
double * elements_;
int numberCliques_;
typedef struct {
unsigned int equality:1; // nonzero if clique is ==
} CliqueType;
CliqueType * cliqueType_;
int * cliqueStart_;
CliqueEntry * cliqueEntry_;
int * oneFixStart_;
int * zeroFixStart_;
int * endFixStart_;
int * whichClique_;
int numberColumns_;
//CliqueEntry * cliqueRow_;
//int * cliqueRowStart_;
};
//#############################################################################
void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
CglCutGenerator.hpp
CglKnapsackCoverUnitTest
void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglTreeInfo.hpp
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglKnapsackCover::findJohnAndEllisCover
int findJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder)
find a cover using the basic logic found in OSL (w/o SOS)
CglKnapsackCover::deleteCliques
void deleteCliques()
Delete all clique information.
CglKnapsackCover::setMaxInKnapsack
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
Definition CglKnapsackCover.hpp:62
CglKnapsackCover::solver_
const OsiSolverInterface * solver_
Cliques **** TEMP so can reference from listing.
Definition CglKnapsackCover.hpp:264
CglKnapsackCover::maxInKnapsack_
int maxInKnapsack_
Maximum in knapsack.
Definition CglKnapsackCover.hpp:255
CglKnapsackCover::~CglKnapsackCover
virtual ~CglKnapsackCover()
Destructor.
CglKnapsackCover::setTestedRowIndices
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
CglKnapsackCover::numRowsToCheck_
int numRowsToCheck_
which rows to look at.
Definition CglKnapsackCover.hpp:258
CglKnapsackCover::complement_
int * complement_
Definition CglKnapsackCover.hpp:266
CglKnapsackCover::whichClique_
int * whichClique_
Clique numbers for one or zero fixes.
Definition CglKnapsackCover.hpp:288
CglKnapsackCover::operator=
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
CglKnapsackCover::deriveAKnapsack
int deriveAKnapsack(const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, bool treatAsLRow, double &b, int *complement, double *xstar, int rowIndex, int numberElements, const int *index, const double *element)
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variabl...
CglKnapsackCover::seqLiftAndUncomplementAndAdd
void seqLiftAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
sequence-dependent lift, uncomplement and add the resulting cut to the cut set
CglKnapsackCover::findExactMostViolatedMinCover
int findExactMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violate...
CglKnapsackCover::expensiveCuts_
bool expensiveCuts_
exactKnapsack can be expensive - this switches off some
Definition CglKnapsackCover.hpp:261
CglKnapsackCover::rowsToCheck_
int * rowsToCheck_
Definition CglKnapsackCover.hpp:259
CglKnapsackCover::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate knapsack cover cuts for the model of the solver interface, si.
CglKnapsackCover::exactSolveKnapsack
int exactSolveKnapsack(int n, double c, double const *pp, double const *ww, double &z, int *x)
A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem.
CglKnapsackCover::zeroFixStart_
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition CglKnapsackCover.hpp:284
CglKnapsackCover::whichRow_
int whichRow_
Definition CglKnapsackCover.hpp:265
CglKnapsackCover::createCliques
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
CglKnapsackCover::cliqueType_
CliqueType * cliqueType_
Definition CglKnapsackCover.hpp:274
CglKnapsackCover::epsilon_
double epsilon_
epsilon
Definition CglKnapsackCover.hpp:249
CglKnapsackCover::findPseudoJohnAndEllisCover
int findPseudoJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a cover using a variation of the logic found in OSL (w/o SOS)
CglKnapsackCover::refreshSolver
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
CglKnapsackCover::numberColumns_
int numberColumns_
Number of columns.
Definition CglKnapsackCover.hpp:290
CglKnapsackCover::findLPMostViolatedMinCover
int findLPMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover proble...
CglKnapsackCover::CglKnapsackCover
CglKnapsackCover(const CglKnapsackCover &)
Copy constructor.
CglKnapsackCover::CglKnapsackCover
CglKnapsackCover()
Default constructor.
CglKnapsackCover::cliqueStart_
int * cliqueStart_
Start of each clique.
Definition CglKnapsackCover.hpp:276
CglKnapsackCover::deriveAKnapsack
int deriveAKnapsack(const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int *complement, double *xstar, int rowIndex, const CoinPackedVectorBase &matrixRow)
CglKnapsackCover::numberCliques_
int numberCliques_
Number of cliques.
Definition CglKnapsackCover.hpp:269
CglKnapsackCover::onetol_
double onetol_
1-epsilon
Definition CglKnapsackCover.hpp:253
CglKnapsackCover::elements_
double * elements_
Definition CglKnapsackCover.hpp:267
CglKnapsackCover::findGreedyCover
int findGreedyCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a minimum cover by a simple greedy approach
CglKnapsackCover::getMaxInKnapsack
int getMaxInKnapsack() const
get limit on number in knapsack
Definition CglKnapsackCover.hpp:65
CglKnapsackCover::liftAndUncomplementAndAdd
int liftAndUncomplementAndAdd(double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
sequence-independent lift and uncomplement and add the resulting cut to the cut set
CglKnapsackCover::cliqueEntry_
CliqueEntry * cliqueEntry_
Entries for clique.
Definition CglKnapsackCover.hpp:278
CglKnapsackCover::liftCoverCut
int liftCoverCut(double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut)
lift the cover inequality
CglKnapsackCover::switchOnExpensive
void switchOnExpensive()
Switch on expensive cuts.
Definition CglKnapsackCover.hpp:71
CglKnapsackCover::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglKnapsackCover::epsilon2_
double epsilon2_
Tolerance to use for violation - bigger than epsilon_.
Definition CglKnapsackCover.hpp:251
CglKnapsackCover::endFixStart_
int * endFixStart_
End of fixes for a column.
Definition CglKnapsackCover.hpp:286
CglKnapsackCover::CglKnapsackCoverUnitTest
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglKnapsackCover::liftUpDownAndUncomplementAndAdd
void liftUpDownAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs)
sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set
CglKnapsackCover::switchOffExpensive
void switchOffExpensive()
Switch off expensive cuts.
Definition CglKnapsackCover.hpp:68
CglKnapsackCover::oneFixStart_
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition CglKnapsackCover.hpp:281
CglKnapsackCover::clone
virtual CglCutGenerator * clone() const
Clone.
CglKnapsackCover::gubifyCut
int gubifyCut(CoinPackedVector &cut)
For testing gub stuff.
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15
CglKnapsackCover::CliqueType
Clique type.
Definition CglKnapsackCover.hpp:271
CglKnapsackCover::CliqueType::equality
unsigned int equality
Definition CglKnapsackCover.hpp:272
CliqueEntry
Derived class to pick up probing info.
Definition CglTreeInfo.hpp:86
cut
Definition Cgl012cut.hpp:153