Structure updated and intqpipopt files added

1 files changed, 310 insertions, 0 deletions

diff --git a/newstructure/thirdparty/linux/include/coin/CglKnapsackCover.hpp b/newstructure/thirdparty/linux/include/coin/CglKnapsackCover.hpp
new file mode 100644
index 0000000..b0e81d6
--- /dev/null
+++ b/newstructure/thirdparty/linux/include/coin/CglKnapsackCover.hpp
@@ -0,0 +1,310 @@
+// $Id: CglKnapsackCover.hpp 1201 2014-03-07 17:24:04Z forrest $
+// 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);
+  /// For testing gub stuff
+  int gubifyCut(CoinPackedVector & cut);
+public:
+  /** 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);
+private:
+  /// 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