limp-cbc-0.3.2.0: cbits/coin/CglKnapsackCover.hpp
// $Id: CglKnapsackCover.hpp 1123 2013-04-06 20:47:24Z stefan $
// 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"
/** Knapsack Cover Cut Generator Class */
class CglKnapsackCover : public CglCutGenerator {
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
public:
/** A method to set which rows should be tested for knapsack covers */
void setTestedRowIndices(int num, const int* ind);
/**@name Generate Cuts */
//@{
/** Generate knapsack cover cuts for the model of the solver interface, si.
Insert the generated cuts into OsiCut, cs.
*/
virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
//@}
/**@name Constructors and destructors */
//@{
/// Default constructor
CglKnapsackCover ();
/// Copy constructor
CglKnapsackCover (
const CglKnapsackCover &);
/// Clone
virtual CglCutGenerator * clone() const;
/// Assignment operator
CglKnapsackCover &
operator=(
const CglKnapsackCover& rhs);
/// Destructor
virtual
~CglKnapsackCover ();
/// Create C++ lines to get to current state
virtual std::string generateCpp( FILE * fp);
/// This can be used to refresh any information
virtual void refreshSolver(OsiSolverInterface * solver);
//@}
/**@name Sets and gets */
//@{
/// Set limit on number in knapsack
inline void setMaxInKnapsack(int value)
{ if (value>0) maxInKnapsack_ = value;}
/// get limit on number in knapsack
inline int getMaxInKnapsack() const
{return maxInKnapsack_;}
/// Switch off expensive cuts
inline void switchOffExpensive()
{ expensiveCuts_=false;}
/// Switch on expensive cuts
inline void switchOnExpensive()
{ expensiveCuts_=true;}
private:
// Private member methods
/**@name Private methods */
//@{
/** deriveAKnapsack
returns 1 if it is able to derive
a (canonical) knapsack inequality
in binary variables of the form ax<=b
from the rowIndex-th row in the model,
returns 0 otherwise.
*/
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);
/** Find a violated minimal cover from
a canonical form knapsack inequality by
solving the -most- violated cover problem
and postprocess to ensure minimality
*/
int findExactMostViolatedMinCover(
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 problem
*/
int findLPMostViolatedMinCover(
int nCols,
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder);
/// find a minimum cover by a simple greedy approach
int findGreedyCover(
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder
);
/// lift the cover inequality
int liftCoverCut(
double & b,
int nRowElem,
CoinPackedVector & cover,
CoinPackedVector & remainder,
CoinPackedVector & cut );
/// sequence-independent lift and uncomplement and add the resulting cut to the cut set
int liftAndUncomplementAndAdd(
double rowub,
CoinPackedVector & krow,
double & b,
int * complement,
int row,
CoinPackedVector & cover,
CoinPackedVector & remainder,
OsiCuts & cs );
/// sequence-dependent lift, uncomplement and add the resulting cut to the cut set
void seqLiftAndUncomplementAndAdd(
int nCols,
double * xstar,
int * complement,
int row,
int nRowElem,
double & b,
CoinPackedVector & cover, // need not be violated
CoinPackedVector & remainder,
OsiCuts & cs );
/// sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set
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 );
/// find a cover using a variation of the logic found in OSL (w/o SOS)
int findPseudoJohnAndEllisCover (
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & cover,
CoinPackedVector & remainder);
/// find a cover using the basic logic found in OSL (w/o SOS)
int findJohnAndEllisCover (
int row,
CoinPackedVector & krow,
double & b,
double * xstar,
CoinPackedVector & fracCover,
CoinPackedVector & atOnes,
CoinPackedVector & remainder);
/** A C-style implementation of the Horowitz-Sahni exact solution
procedure for solving knapsack problem.
(ToDo: implement the more efficient dynamic programming approach)
(Reference: Martello and Toth, Knapsack Problems, Wiley, 1990, p30.)
*/
int exactSolveKnapsack(
int n,
double c,
double const *pp,
double const *ww,
double & z,
int * x);
/** Creates cliques for use by probing.
Only cliques >= minimumSize and < maximumSize created
Can also try and extend cliques as a result of probing (root node).
Returns number of cliques found.
*/
int createCliques( OsiSolverInterface & si,
int minimumSize=2, int maximumSize=100, bool extendCliques=false);
/// Delete all clique information
void deleteCliques();
//@}
// Private member data
/**@name Private member data */
//@{
/// epsilon
double epsilon_;
/// Tolerance to use for violation - bigger than epsilon_
double epsilon2_;
/// 1-epsilon
double onetol_;
/// Maximum in knapsack
int maxInKnapsack_;
/** which rows to look at. If specified, only these rows will be considered
for generating knapsack covers. Otherwise all rows will be tried */
int numRowsToCheck_;
int* rowsToCheck_;
/// exactKnapsack can be expensive - this switches off some
bool expensiveCuts_;
/// Cliques
/// **** TEMP so can reference from listing
const OsiSolverInterface * solver_;
int whichRow_;
int * complement_;
double * elements_;
/// Number of cliques
int numberCliques_;
/// Clique type
typedef struct {
unsigned int equality:1; // nonzero if clique is ==
} cliqueType;
cliqueType * cliqueType_;
/// Start of each clique
int * cliqueStart_;
/// Entries for clique
cliqueEntry * cliqueEntry_;
/** Start of oneFixes cliques for a column in matrix or -1 if not
in any clique */
int * oneFixStart_;
/** Start of zeroFixes cliques for a column in matrix or -1 if not
in any clique */
int * zeroFixStart_;
/// End of fixes for a column
int * endFixStart_;
/// Clique numbers for one or zero fixes
int * whichClique_;
/// Number of columns
int numberColumns_;
/** For each column with nonzero in row copy this gives a clique "number".
So first clique mentioned in row is always 0. If no entries for row
then no cliques. If sequence > numberColumns then not in clique.
*/
//cliqueEntry * cliqueRow_;
/// cliqueRow_ starts for each row
//int * cliqueRowStart_;
//@}
};
//#############################################################################
/** A function that tests the methods in the CglKnapsackCover class. The
only reason for it not to be a member method is that this way it doesn't
have to be compiled into the library. And that's a gain, because the
library should be compiled with optimization on, but this method should be
compiled with debugging. */
void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif