/usr/include/coin/CglOddHole.hpp is in coinor-libcgl-dev 0.58.4-2ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 | // $Id: CglOddHole.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 CglOddHole_H
#define CglOddHole_H
#include <string>
#include "CglCutGenerator.hpp"
/** Odd Hole Cut Generator Class */
class CglOddHole : public CglCutGenerator {
friend void CglOddHoleUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
public:
/**@name Generate Cuts */
//@{
/** Generate odd hole cuts for the model of the solver interface, si.
This looks at all rows of type sum x(i) <= 1 (or == 1) (x 0-1)
and sees if there is an odd cycle cut. See Grotschel, Lovasz
and Schrijver (1988) for method.
This is then lifted by using the corresponding Chvatal cut i.e.
Take all rows in cycle and add them together. RHS will be odd so
weaken all odd coefficients so 1.0 goes to 0.0 etc - then
constraint is sum even(j)*x(j) <= odd which can be replaced by
sum (even(j)/2)*x(j) <= (odd-1.0)/2.
A similar cut can be generated for sum x(i) >= 1.
Insert the generated cuts into OsiCut, cs.
This is only done for rows with unsatisfied 0-1 variables. If there
are many of these it will be slow. Improvements would do a
randomized subset and also speed up shortest path algorithm used.
*/
virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
const CglTreeInfo info = CglTreeInfo());
//@}
/**@name Create Row List */
//@{
/// Create a list of rows which might yield cuts
/// this is to speed up process
/// The possible parameter is a list to cut down search
void createRowList( const OsiSolverInterface & si,
const int * possible=NULL);
/// This version passes in a list - 1 marks possible
void createRowList(int numberRows, const int * whichRow);
//@}
/**@name Create Clique List */
//@{
/// Create a list of extra row cliques which may not be in matrix
/// At present these are classical cliques
void createCliqueList(int numberCliques, const int * cliqueStart,
const int * cliqueMember);
//@}
/**@name Number Possibilities */
//@{
/// Returns how many rows might give odd hole cuts
int numberPossible();
//@}
/**@name Gets and Sets */
//@{
/// Minimum violation
double getMinimumViolation() const;
void setMinimumViolation(double value);
/// Minimum violation per entry
double getMinimumViolationPer() const;
void setMinimumViolationPer(double value);
/// Maximum number of entries in a cut
int getMaximumEntries() const;
void setMaximumEntries(int value);
//@}
/**@name Constructors and destructors */
//@{
/// Default constructor
CglOddHole ();
/// Copy constructor
CglOddHole (
const CglOddHole &);
/// Clone
virtual CglCutGenerator * clone() const;
/// Assignment operator
CglOddHole &
operator=(
const CglOddHole& rhs);
/// Destructor
virtual
~CglOddHole ();
/// This can be used to refresh any inforamtion
virtual void refreshSolver(OsiSolverInterface * solver);
//@}
private:
// Private member methods
/**@name Private methods */
//@{
/// Generate cuts from matrix copy and solution
/// If packed true then <=1 rows, otherwise >=1 rows.
void generateCuts(const OsiRowCutDebugger * debugger,
const CoinPackedMatrix & rowCopy,
const double * solution, const double * dj,
OsiCuts & cs, const int * suitableRow,
const int * fixedColumn,const CglTreeInfo info,
bool packed);
//@}
// Private member data
/**@name Private member data */
//@{
/// list of suitableRows
int * suitableRows_;
/// start of each clique
int * startClique_;
/// clique members
int * member_;
/// epsilon
double epsilon_;
/// 1-epsilon
double onetol_;
/// Minimum violation
double minimumViolation_;
/// Minimum violation per entry
double minimumViolationPer_;
/// Maximum number of entries in a cut
int maximumEntries_;
/// number of rows when suitability tested
int numberRows_;
/// number of cliques
int numberCliques_;
//@}
};
//#############################################################################
/** A function that tests the methods in the CglOddHole 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 CglOddHoleUnitTest(const OsiSolverInterface * siP,
const std::string mpdDir );
#endif
|