My Project
OSBearcatSolverXij.h
Go to the documentation of this file.
1/* $Id: OSBearcatSolverXij.h 3038 2009-11-07 11:43:44Z kmartin $ */
13#ifndef OSBEARCATSOLVERXIJ_H
14#define OSBEARCATSOLVERXIJ_H
15
16#include "OSDecompSolver.h"
18#include "OSInstance.h"
19#include "OSOption.h"
20#include "ClpSimplex.hpp"
21#include "OSCoinSolver.h"
22#include <map>
23// --------------------------------------------------------------------- //
30// --------------------------------------------------------------------- //
32public:
33
34
35
36
37/***************** Bearcat Specific Solver Parameters ***********************/
38 //kipp move to the method
39 std::map<int, std::string> m_tmpVarMap;
40
44 std::map<std::pair<int, int>,int>m_xVarIndexMap;
45
51
52
53 std::string m_initOSiLFile;
54
59 std::map<int, std::map<int, std::vector<int> > > m_initSolMap;
60
65 std::vector<CoinSolver*> m_multCommodCutSolvers;
66
71
77
78
79
80
85
91
92
93
99
100
105
108
114
117
119 std::string* m_nodeName;
120
122 double* m_cost;
123
128
132 double** m_rc;
133
134
135 //will be the optimal reduced cost for each hub
136 double* m_optValHub;
137
138
139 //start variables for the q-route dynamic program
140 double** m_u;
141 double** m_v;
142 int** m_px;
143 int** m_tx;
144 double** m_g;
146 //end variables for the q-route dynamic programming solution
147
148 //variables for the outer dynamic program
149 //get the optimal l value for each route
150 int* m_optL; //size is number of routes
151 int* m_optD; //size is number of routes
152 double** m_vv;
153 int** m_vvpnt;
154 //end of variable on the outer dynamic program
155
156
159
160
161 //below is a scatter array we scatter into in order
162 //to multiply the transformation matrix times the A matrix
164
165 //arguments for getColumns
168 double* m_costVec;
171
172 //arguments for getRows
176 double* m_newRowUB;
177 double* m_newRowLB;
178
179 //arguments for the getBranchingCut
182 //end arguments for the getBranchingCut
183
184
185
186
187
188 //kipp -- be carefull does m_thetaCost have
189 // artificial variables -- it is
190 double* m_thetaCost;
191
197
198
205
206
212
213 //
215
216 //the Clp model
218
219 //create the initial restricted master
221
222
223 //this method generates the instance for
224 //separating the tour breaking constraints
226
228 // note -- this c vector is only for hub k
229 double qrouteCost(const int& k, const int& l, const double* c, int* kountVar) ;
230
231 //this c vector is for the entire cost vector
232 void getOptL( double** c) ;
233
234
248 void getCutsTheta(const double* thetaVar, const int numThetaVar,
249 int &numNewRows, int* &numNonz, int** &colIdx,
250 double** &values, double* &rowLB, double* &rowUB) ;
251
252
266 void getCutsX(const double* xVar, const int numXVar,
267 int &numNewRows, int* &numNonz, int** &colIdx,
268 double** &values, double* &rowLB, double* &rowUB) ;
269
270
289 virtual void getBranchingCut(const double* thetaVar, const int numThetaVar,
290 const std::map<int, int> &varConMap, int &varIdx, int &numNonz,
291 int* &indexes, double* &values) ;
292
293
294
316 virtual void getBranchingCut(const int* thetaIdx, const double* theta,
317 const int numThetaVar, const std::map<int, int> &varConMap,
318 int &varIdx, int &numNonz, int* &indexes, double* &values) ;
319
320
321
337 void getCutsMultiCommod(const double* thetaVar, const int numThetaVar,
338 int &numNewRows, int* &numNonz, int** &colIdx,
339 double** &values, double* &rowLB, double* &rowUB) ;
340
341
342
352 int getBranchingVar(const double* theta, const int numThetaVar ) ;
353
354
367 int getBranchingVar(const int* thetaIdx, const double* theta, const int numThetaVar ) ;
368
369
383 virtual void getColumns(const double* yA, const int numARows,
384 const double* yB, const int numBRows,
385 int &numNewColumns, int* &numNonz, double* &cost,
386 int** &rowIdx, double** &values, double &lowerBound) ;
387
388
389
391
397 void getVariableIndexMap();
398
399
405 void permuteHubs();
406
407
408 //some utility methods are below
409
416 void calcReducedCost(const double* yA, const double* yB );
417
418 //these are the variable in x(i, j) space
419 void createVariableNames( );
420
421 //this is the matrix that says we must visit each node
422 //this A matrix defines the "coupling constraints"
423 void createAmatrix();
424
428 virtual void initializeDataStructures();
429
433 void getInitialSolution();
434
435 virtual void resetMaster( std::map<int, int> &inVars,
436 OsiSolverInterface *si );
437
438
453 double getRouteDistance(int numNodes, int hubIndex,
454 CoinSolver* solver, std::vector<int> zk,
455 double* xVar);
456
457
468 CoinSolver* getTSP(int numNodes, double* cost);
469
470
471
482 CoinSolver* getMultiCommodInstance(int hubIndex);
483
484
495 void getFeasibleSolution();
496
497
503 bool OneOPT();
504
505
506 //this method gets called when we are done
507 virtual void pauHana(std::vector<int> &m_zOptIndexes,
508 std::vector<double> &m_zRootLPx_vals,
509 int numNodes, int numColsGen, std::string message);
510
514 double calcNonlinearRelax( std::vector<double> &m_zRootLPx_vals);
515
516
522
528
529
535
536
537 class Factory;
539
540 public:
541
543
544 }
545
547
548 }
549
551
552 };// end class OSDecompSolverFactory
553
554
555};//end class OSBearcatSolverXij
556
557#endif
558
OSOption * osoption
Implements a solve method for the Coin solvers.
int * m_demand
m_demand is the vector of node demands
std::map< int, std::string > m_tmpVarMap
double getRouteDistance(int numNodes, int hubIndex, CoinSolver *solver, std::vector< int > zk, double *xVar)
call this method to get a minimum TSP tour for a given assignment of nodes to routes INPUT: int numNo...
double * m_cost
the distance/cost vectors
double calcNonlinearRelax(std::vector< double > &m_zRootLPx_vals)
calculate the nonlinear relaxation value for an LP solution
std::string * m_nodeName
m_nodeName is the vector of node names
int * m_upperBoundL
largest possible L-value on a route – this will be the minimum of m_routeCapacity and total demand
void getCutsMultiCommod(const double *thetaVar, const int numThetaVar, int &numNewRows, int *&numNonz, int **&colIdx, double **&values, double *&rowLB, double *&rowUB)
This is the routine that generates the multi-item cuts.
int * m_BmatrixRowIndex
m_BmatrixRowIndex holds the index of the convexity row that the constraint corresponds to,...
CoinSolver * getTSP(int numNodes, double *cost)
call this method to get a TSP instance
int * m_lowerBoundL
smallest possible L-value on a route for now this will equal
int * m_hubPoint
m_hubPoint[ k] points to the the k'th hub that we use in getOptL
ClpSimplex * m_separationClpModel
int * m_separationIndexMap
m_separationIndexMap maps the variable index into the appropriate row in the separation problem for t...
double qrouteCost(const int &k, const int &l, const double *c, int *kountVar)
kipp – document
void getVariableIndexMap()
this method will populate: std::map<std::pair<int, int>,int>m_xVarIndexMap this gives us
int * m_routeMinPickup
the minimum number of students that we pickup on a route this can vary with the route/hub
double ** m_rc
the reduced cost vector for each k, we asssume order is (l, i, j)
int m_maxThetaNonz
m_maxMasterNonz is the maximumn number of nonzero elements we allow in the transformation matrix betw...
virtual OSInstance * getInitialRestrictedMaster()
OSInstance* OSBearcatSolverXij::getInitialRestrictedMaster( ){.
~OSBearcatSolverXij()
Default Destructor.
void getInitialSolution()
generate an intitial feasible solution in theta space for the initial master
std::map< std::pair< int, int >, int > m_xVarIndexMap
m_xVarIndexMap takes a variable indexed by (i,j) and returns the index of the variable in one dimensi...
void getOptions(OSOption *osoption)
virtual void resetMaster(std::map< int, int > &inVars, OsiSolverInterface *si)
INPUT:
int m_upperBoundLMax
largest possible L-value over all routes
virtual void initializeDataStructures()
allocate memory and initialize arrays
virtual void pauHana(std::vector< int > &m_zOptIndexes, std::vector< double > &m_zRootLPx_vals, int numNodes, int numColsGen, std::string message)
OSInstance * m_osinstanceSeparation
std::map< int, std::map< int, std::vector< int > > > m_initSolMap
the index on the outer map is on the solution number, the index on the inner map indexes the route nu...
void permuteHubs()
this method will calculate a permuation of the hubs so that they are in ascending order,...
virtual void getBranchingCut(const double *thetaVar, const int numThetaVar, const std::map< int, int > &varConMap, int &varIdx, int &numNonz, int *&indexes, double *&values)
RETURN VALUES: varIdx – the variable number x_{ij} for branching numNonz – number of theta indexes in...
int getBranchingVar(const double *theta, const int numThetaVar)
RETURN VALUES: return the integer index of a fractional x_{ij} variable.
int m_minDemand
m_minDemand is the value of the minimum demand node – it is not the minimum demand that must be carri...
std::vector< CoinSolver * > m_multCommodCutSolvers
m_multCommodCutSolvers is a vector of solvers, one solver for each hub, used to find multicommodity f...
OSInstance * getSeparationInstance()
bool m_costSetInOption
m_costSetInOption is true if the costs are set using the OSOption file
void getFeasibleSolution()
call this method to get generate an instance of the generalized assignment problem and find a feasibl...
int * m_routeCapacity
the route capacity – bus seating limit this can vary with the route/hub
OSBearcatSolverXij()
Default Constructor.
bool OneOPT()
try and find a feasible solution, return false if solution not feasible
bool m_use1OPTstart
if m_use1OPTstart is true we use the option file to fix the nodes to hubs found by SK's 1OPT heuristi...
int * m_convexityRowIndex
m_convexityRowIndex holds the index of the convexity row that the theta columns are in.
virtual void getColumns(const double *yA, const int numARows, const double *yB, const int numBRows, int &numNewColumns, int *&numNonz, double *&cost, int **&rowIdx, double **&values, double &lowerBound)
RETURN VALUES: int numNewColumns – number of new columns generated int* numNonz – number of nonzeros ...
void getCutsX(const double *xVar, const int numXVar, int &numNewRows, int *&numNonz, int **&colIdx, double **&values, double *&rowLB, double *&rowUB)
RETURN VALUES: int numNewRows – number of new rows generated int* numNonz – number of nonzeros in eac...
void getCutsTheta(const double *thetaVar, const int numThetaVar, int &numNewRows, int *&numNonz, int **&colIdx, double **&values, double *&rowLB, double *&rowUB)
RETURN VALUES: int numNewRows – number of new rows generated int* numNonz – number of nonzeros in eac...
CoinSolver * getMultiCommodInstance(int hubIndex)
call this method to get an instance that is used to generate a multicommodity cut
void calcReducedCost(const double *yA, const double *yB)
calculate the reduced costs c – input of the objective function costs yA – dual values on node assign...
The in-memory representation of an OSiL instance..
The Option Class.
Definition OSOption.h:3565