Cgl 0.60.3
CglLandPSimplex.hpp
Go to the documentation of this file.
1// Copyright (C) 2005-2009 Pierre Bonami and others. All Rights Reserved.
2// Author: Pierre Bonami
3// Tepper School of Business
4// Carnegie Mellon University, Pittsburgh, PA 15213
5// Date: 21/07/05
6//
7// $Id$
8//
9// This code is licensed under the terms of the Eclipse Public License (EPL).
10//---------------------------------------------------------------------------
11#ifndef CglLandPSimplex_H
12#define CglLandPSimplex_H
13
14#include <iostream>
15#include <vector>
16
17#include "CglConfig.h"
18#include "CglLandP.hpp"
19
20#include "OsiSolverInterface.hpp"
21#include "CoinMessage.hpp"
22#include "CoinMessageHandler.hpp"
23#include "CoinWarmStartBasis.hpp"
24#include "CoinPackedMatrix.hpp"
25
26#ifdef COIN_HAS_OSICLP
27#include "OsiClpSolverInterface.hpp"
28#endif
29
30#include "CglLandPTabRow.hpp"
31#include "CglLandPUtils.hpp"
32#include "CglLandPMessages.hpp"
33
34//#define APPEND_ROW
35#define OLD_COMPUTATION
36
37namespace LAP
38{
40class DebugData;
41
43{
44public:
46 CglLandPSimplex(const OsiSolverInterface &si,
47 const CglLandP::CachedData &cached,
48 const CglLandP::Parameters &params,
49 Validator &validator);
53 void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
55 bool resetSolver(const CoinWarmStartBasis * basis);
57 bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
59 bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters & params);
60
64 int generateExtraCut(int i, const CglLandP::CachedData & cached,
65 const CglLandP::Parameters& params);
66
68 const CglLandP::Parameters & params) ;
69
71 int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq);
72
73 void setLogLevel(int level)
74 {
75 handler_->setLogLevel(level);
76 }
77
78
79 void setSi(OsiSolverInterface *si)
80 {
81 si_ = si;
82#ifdef COIN_HAS_OSICLP
83 OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_);
84 if (clpSi)
85 {
86 clp_ = clpSi;
87 }
88#endif
89 }
90 void freeSi()
91 {
92 assert(si_ != NULL);
93 delete si_;
94 si_ = NULL;
95#ifdef COIN_HAS_OSICLP
96 clp_ = NULL;
97#endif
98 }
99
101 {
102 return cuts_;
103 }
104 void loadBasis(const OsiSolverInterface &si,
105 std::vector<int> &M1, std::vector<int> &M2,
106 int k);
107
108
109 int getNumCols() const
110 {
111 return ncols_;
112 }
113
114 int getNumRows() const
115 {
116 return nrows_;
117 }
118
119 const CoinWarmStartBasis * getBasis() const
120 {
121 return basis_;
122 }
123 const int * getNonBasics() const
124 {
125 return nonBasics_;
126 }
127
128 const int * getBasics() const
129 {
130 return basics_;
131 }
132
133 void outPivInfo(int ncuts)
134 {
135 handler_->message(RoundStats, messages_)<<ncuts<<numPivots_
137 <<numIncreased_<<CoinMessageEol;
138 }
139#ifdef APPEND_ROW
141 void append_row(int row_num, bool modularize) ;
143 void update_row(TabRow &row);
144
145 void check_mod_row(TabRow &row);
146#endif
147protected:
149 bool changeBasis(int incoming, int leaving, int direction,
150#ifndef OLD_COMPUTATION
151 bool recompute_source_row,
152#endif
153 bool modularize);
157 int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows);
159 int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
161 int fastFindBestPivotColumn(int direction, int gammaSign,
162 double pivotTol, double rhsTol,
163 bool reducedSpace,
164 bool allowNonImproving,
165 double &bestSigma, bool modularize);
166
174 int findBestPivot(int &leaving, int & direction,
175 const CglLandP::Parameters & params);
176
177
180 double computeCglpObjective(const TabRow & row, bool modularize = false) const;
184 inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
187 inline double newRowCoefficient(int j, double gamma) const;
189 void createIntersectionCut(TabRow & row, OsiRowCut &cut) const;
191 double normalizationFactor(const TabRow & row) const;
193 void scaleCut(OsiRowCut & cut, double factor) const;
195 // void createIntersectionCut(double * row);
197 void createMIG( TabRow & row, OsiRowCut &cut) const;
199 void pullTableauRow(TabRow & row) const;
201 void adjustTableauRow(int var, TabRow & row, int direction);
203 void resetOriginalTableauRow(int var, TabRow & row, int direction);
205 inline double getLoBound(int index) const
206 {
207 return lo_bounds_[original_index_[index]];
208 }
210 inline double getUpBound(int index) const
211 {
212 return up_bounds_[original_index_[index]];
213 }
215 inline double getColsolToCut(int index) const
216 {
217 return colsolToCut_[original_index_[index]];
218 }
219 bool isGtConst(int index) const
220 {
221 return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09);
222 }
224 inline void setColsolToCut(int index, double value)
225 {
226 colsolToCut_[original_index_[index]] = value;
227 }
229 inline CoinWarmStartBasis::Status getStatus(int index) const
230 {
231 if (index < ncols_) return basis_->getStructStatus(index);
232 return basis_->getArtifStatus(index - ncols_);
233 }
235 inline bool isInteger(int index) const
236 {
237 return integers_[original_index_[index]];
238 }
243 double normedCoef(double a, int ii) const
244 {
245 if (norm_weights_.empty())
246 {
247 return a;
248 }
249 else
250 {
251 return a*norm_weights_[ii];
252 }
253 }
255 void printTableau(std::ostream & os);
256
260 void printTableauLateX(std::ostream & os);
261 void printRowLateX(std::ostream & os, int i);
262 void printCutLateX(std::ostream & os, int i);
263
265 void printCglpBasis(std::ostream& os = std::cout);
267 void get_M1_M2_M3(const TabRow & row,
268 std::vector<int> &M1,
269 std::vector<int> &M2,
270 std::vector<int> &M3);
272 void eliminate_slacks(double * vec) const;
273private:
280#ifdef COIN_HAS_OSICLP
282 OsiClpSolverInterface * clp_;
283#endif
284
286 void updateM1_M2_M3(TabRow & row, double tolerance, bool alwaysComputeCheap);
288 void removeRows(int nDelete, const int * rowsIdx);
289
290
291 void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s);
292
293
296
302#ifndef NDBEUG
304#endif
306 CoinPackedVector gammas_;
308 std::vector<double> rWk1_;
310 std::vector<double> rWk2_;
312 std::vector<double> rWk3_;
314 std::vector<double> rWk4_;
316 std::vector<int> rIntWork_;
318 bool * rowFlags_;
320 std::vector<bool> col_in_subspace;
324 int * basics_;
328 std::vector<int> M1_;
330 std::vector<int> M2_;
332 std::vector<int> M3_;
334 double sigma_;
336 CoinWarmStartBasis * basis_;
338 double * colsolToCut_;
340 double * colsol_;
349 // for fast access to lower bounds (both cols and rows)
350 std::vector<double> lo_bounds_;
351 // for fast access to upper bounds (both cols and rows)
352 std::vector<double> up_bounds_;
358 const bool * integers_;
360 std::vector<int> original_index_;
366
367 OsiSolverInterface * si_;
370 bool own_;
374 std::vector<double> norm_weights_;
377
382
389
391 CoinMessageHandler * handler_;
393 CoinMessages messages_;
394#ifndef NDEBUG
396#endif
397
398protected:
402 double computeCglpRedCost(int direction, int gammaSign, double tau);
406 double computeCglpObjective(double gamma, bool strengthen, TabRow &row);
408 double computeCglpObjective(double gamma, bool strengthen);
411 int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
413 int findBestPivotColumn(int direction,
414 double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
415 bool modularize);
416#if 1
417 int plotCGLPobj(int direction, double gammaTolerance,
418 double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
419#endif
420
422};
423
424
426double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
427{
428 // double ratio = beta/(1-beta);
429 if ( (!integers_[i]))
430 return intersectionCutCoef(alpha_i, beta);
431 else
432 {
433 double f_i = alpha_i - floor(alpha_i);
434 if (f_i < beta)
435 return f_i*(1- beta);
436 else
437 return (1 - f_i)*beta;//(1-beta);
438 }
439}
440
443double
444CglLandPSimplex::newRowCoefficient(int j, double gamma) const
445{
446 return row_k_[j] + gamma * row_i_[j];
447}
448
449}
450#endif
#define OLD_COMPUTATION
Class storing parameters.
Definition: CglLandP.hpp:108
RhsWeightType
RHS weight in normalization.
Definition: CglLandP.hpp:101
Normalization
Normalization.
Definition: CglLandP.hpp:83
void get_M1_M2_M3(const TabRow &row, std::vector< int > &M1, std::vector< int > &M2, std::vector< int > &M3)
Put variables in M1 M2 and M3 according to their sign.
OsiSolverInterface * si_
Pointer to the solver interface.
void setSi(OsiSolverInterface *si)
void setLogLevel(int level)
int nrows_orig_
cached numrows in original problem
const int * getBasics() const
int nrows_
Cached number of rows in reduced size problem.
TabRow row_k_
Source row for cut.
void resetOriginalTableauRow(int var, TabRow &row, int direction)
reset the tableau row after a call to adjustTableauRow
const bool * integers_
pointer to array of integer info for both structural and slacks
bool inDegenerateSequence_
Say if we are in a sequence of degenerate pivots.
void createMIG(TabRow &row, OsiRowCut &cut) const
Create strenghtened row.
const CoinWarmStartBasis * getBasis() const
std::vector< double > rWk1_
first work vector in row space.
double getLoBound(int index) const
Get lower bound for variable or constraint.
void printCglpBasis(std::ostream &os=std::cout)
Print CGLP basis corresponding to current tableau and source row.
bool * rowFlags_
Flag rows which we don't want to try anymore.
void setColsolToCut(int index, double value)
Access to value in solution to cut (indexed in reduced problem)
void updateM1_M2_M3(TabRow &row, double tolerance, bool alwaysComputeCheap)
Update values in M1 M2 and M3 before an iteration.
void eliminate_slacks(double *vec) const
Put a vector in structural sapce.
void scaleCut(OsiRowCut &cut, double factor) const
Scale the cut by factor.
int ncols_
cached number of columns in reduced size problem
void genThisBasisMigs(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
std::vector< int > M2_
Stores the variables which are always in M2 for a given k.
int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Find extra constraints in current tableau.
std::vector< int > M3_
Stores the variables which could be either in M1 or M2.
int numPivots_
Record the number of pivots.
double computeCglpRedCost(int direction, int gammaSign, double tau)
Compute the reduced cost of Cglp.
bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters &params)
Find Gomory cut (i.e.
void adjustTableauRow(int var, TabRow &row, int direction)
Adjust the row of the tableau to reflect leaving variable direction.
CglLandPSimplex(const OsiSolverInterface &si, const CglLandP::CachedData &cached, const CglLandP::Parameters &params, Validator &validator)
Usefull onstructor.
bool optimize(int var, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Perfom pivots to find the best cuts.
void createIntersectionCut(TabRow &row, OsiRowCut &cut) const
Create the intersection cut of row k.
double normalizationFactor(const TabRow &row) const
Compute the normalization factor of the cut.
void printRowLateX(std::ostream &os, int i)
int numSourceRowEntered_
Record the number of times the source row entered the basis.
bool isInteger(int index) const
Say if variable index by i in current tableau is integer.
CglLandPSimplex(const CglLandPSimplex &)
No copy constructor.
int * basics_
Store the basics variable.
CoinMessages messages_
Messages.
std::vector< int > rIntWork_
integer valued work vector on the rows
double rhs_weight_
Weight for rhs of normalization constraint.*‍/.
void compute_p_q_r_s(double gamma, int gammaSign, double &p, double &q, double &r, double &s)
Cuts cuts_
Stores extra cuts which are generated along the procedure.
int fastFindCutImprovingPivotRow(int &direction, int &gammaSign, double tolerance, bool flagPositiveRows)
Find a row which can be used to perform an improving pivot the fast way (i.e., find the leaving varia...
double * colsolToCut_
Pointer to the solution to cut (need to be modified after each pivot because we are only considering ...
Validator & validator_
A pointer to a cut validator.
int generateExtraCut(int i, const CglLandP::CachedData &cached, const CglLandP::Parameters &params)
Generate a constrainte for a row of the tableau different from the source row.
std::vector< double > rWk3_
third work vector in row space.
std::vector< double > up_bounds_
std::vector< bool > col_in_subspace
Flag columns which are in the subspace (usualy remove nonbasic structurals in subspace)
int insertAllExtr(OsiCuts &cs, CoinRelFltEq eq)
insert all extra cuts in cs.
double newRowCoefficient(int j, double gamma) const
return the coefficient of the new row (combining row_k + gamma row_i).
double chosenReducedCostVal_
Value for the reduced cost chosen for pivoting.
bool own_
Own the data or not?
CoinPackedVector gammas_
vector to sort the gammas
TabRow original_row_k_
Original version of source row (without modularization).
void printEverything()
Print everything .
int plotCGLPobj(int direction, double gammaTolerance, double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize)
int findBestPivot(int &leaving, int &direction, const CglLandP::Parameters &params)
Find incoming and leaving variables which lead to the most violated adjacent normalized lift-and-proj...
TabRow row_i_
Row of leaving candidate.
int nNegativeRcRows_
number of rows with a <0 rc in current iteration
~CglLandPSimplex()
Destructor.
int ncols_orig_
cached numcols in original problem
int findCutImprovingPivotRow(int &direction, int &gammaSign, double tolerance)
Find a row which can be used to perform an improving pivot return index of the cut or -1 if none exis...
int * nonBasics_
Stores the nonBasicVariables.
bool * colCandidateToLeave_
Flag columns which have to be considered for leaving the basis.
void printTableauLateX(std::ostream &os)
print the tableau of current basis.
double * colsol_
Pointer to the current basic solution.
CoinMessageHandler * handler_
Message handler.
void loadBasis(const OsiSolverInterface &si, std::vector< int > &M1, std::vector< int > &M2, int k)
double computeCglpObjective(double gamma, bool strengthen)
Compute the objective value of the Cglp with linear combintation of the row_k_ and gamma row_i_.
const int * getNonBasics() const
double computeCglpObjective(const TabRow &row, bool modularize=false) const
Compute the objective value of the Cglp for given row and rhs (if strengthening shall be applied row ...
double computeRedCostConstantsInRow()
Compute the value of sigma and thau (which are constants for a row i as defined in Mike Perregaard th...
std::vector< double > norm_weights_
Weights for the normalization constraint.
CoinWarmStartBasis::Status getStatus(int index) const
Get the basic status of a variable (structural or slack).
void pullTableauRow(TabRow &row) const
Get the row i of the tableau.
std::vector< int > original_index_
Original index of variable before deletions.
int rescanReducedCosts(int &direction, int &gammaSign, double tolerance)
Rescan reduced costs tables.
double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
return the coefficients of the strengthened intersection cut takes one extra argument seens needs to ...
bool resetSolver(const CoinWarmStartBasis *basis)
reset the solver to optimal basis
CglLandPSimplex()
No default constructor.
void printCutLateX(std::ostream &os, int i)
int fastFindBestPivotColumn(int direction, int gammaSign, double pivotTol, double rhsTol, bool reducedSpace, bool allowNonImproving, double &bestSigma, bool modularize)
Find the column which leads to the best cut (i.e., find incoming variable).
void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type, CglLandP::RhsWeightType rhs)
Compute normalization weights.
void outPivInfo(int ncuts)
std::vector< int > M1_
Stores the variables which are always in M1 for a given k.
int numIncreased_
Record the number of times that sigma increased.
std::vector< double > rWk2_
scond work vector in row space.
int findBestPivotColumn(int direction, double pivotTol, bool reducedSpace, bool allowDegeneratePivot, bool modularize)
Find the column which leads to the best cut (i.e., find incoming variable).
double computeCglpObjective(double gamma, bool strengthen, TabRow &row)
Compute the objective value of the Cglp with linear combintation of the two rows by gamma.
double normedCoef(double a, int ii) const
Evenutaly multiply a by w if normed_weights_ is not empty.
CglLandPSimplex & operator=(const CglLandPSimplex &)
No assignment operator.
std::vector< double > lo_bounds_
void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace=0)
Update cached information in case of basis change in a round.
CoinWarmStartBasis * basis_
Keep track of basis status.
double getColsolToCut(int index) const
Access to value in solution to cut (indexed in reduced problem)
std::vector< double > rWk4_
fourth work vector in row space.
double getUpBound(int index) const
Get upper bound for variable or constraint.
bool changeBasis(int incoming, int leaving, int direction, bool modularize)
Perform a change in the basis (direction is 1 if leaving variable is going to ub, 0 otherwise)
void removeRows(int nDelete, const int *rowsIdx)
Remove rows from current tableau.
bool checkBasis()
Check that the basis is correct.
bool isGtConst(int index) const
void printTableau(std::ostream &os)
print the tableau of current basis.
double sigma_
stores the cglp value of the normalized cut obtained from row k_
Class to validate or reject a cut.
Performs one round of Lift & Project using CglLandPSimplex to build cuts.
Definition: CglLandP.hpp:25
double intersectionCutCoef(double alpha_i, double beta)
return the coefficients of the intersection cut
Some informations that will be changed by the pivots and that we want to keep.
Definition: CglLandP.hpp:242
To store extra cuts generated by columns from which they origin.