Cgl/Doxygen/CglKnapsackCover_8hpp_source.html

// $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