My Project
OSBearcatSolverXkij.h
Go to the documentation of this file.
1/* $Id: OSBearcatSolverXkij.h 3038 2009-11-07 11:43:44Z kmartin $ */
13#ifndef OSBEARCATSOLVERXKIJ_H
14#define OSBEARCATSOLVERXKIJ_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
39
40
41
42
43 std::string m_initOSiLFile;
44
49 std::map<int, std::map<int, std::vector<int> > > m_initSolMap;
50
51
52
53
54
59
65
66
67
68
73
79
80
81
87
88
93
96
102
105
107 double** m_cost;
108
112 double** m_rc;
113
114
115 //will be the optimal reduced cost for each hub
116 double* m_optValHub;
117
118
119 //start variables for the q-route dynamic program
120 double** m_u;
121 double** m_v;
122 int** m_px;
123 int** m_tx;
124 double** m_g;
126 //end variables for the q-route dynamic programming solution
127
128 //variables for the outer dynamic program
129 //get the optimal l value for each route
130 int* m_optL; //size is number of routes
131 int* m_optD; //size is number of routes
132 double** m_vv;
133 int** m_vvpnt;
134 //end of variable on the outer dynamic program
135
136
139
140
141 //below is a scatter array we scatter into in order
142 //to multiply the transformation matrix times the A matrix
144
145 //arguments for getColumns
148 double* m_costVec;
151
152 //arguments for getRows
156 double* m_newRowUB;
157 double* m_newRowLB;
158
159 //arguments for the getBranchingCut
162 //end arguments for the getBranchingCut
163
164
165
166
167
168 //kipp -- be carefull does m_thetaCost have
169 // artificial variables -- it is
170 double* m_thetaCost;
171
177
178
184
185 //
187
188 //the Clp model
190
191 //create the initial restricted master
193
194
195 //this method generates the instance for
196 //separating the tour breaking constraints
198
200 // note -- this c vector is only for hub k
201 double qrouteCost(const int& k, const int& l, const double* c, int* kountVar) ;
202
203 //this c vector is for the entire cost vector
204 void getOptL( double** c) ;
205
206
220 void getCutsTheta(const double* thetaVar, const int numThetaVar,
221 int &numNewRows, int* &numNonz, int** &colIdx,
222 double** &values, double* &rowLB, double* &rowUB) ;
223
224
238 void getCutsX(const double* xVar, const int numXVar,
239 int &numNewRows, int* &numNonz, int** &colIdx,
240 double** &values, double* &rowLB, double* &rowUB) ;
241
242
261 virtual void getBranchingCut(const double* thetaVar, const int numThetaVar,
262 const std::map<int, int> &varConMap, int &varIdx, int &numNonz,
263 int* &indexes, double* &values) ;
264
265
266
288 virtual void getBranchingCut(const int* thetaIdx, const double* theta,
289 const int numThetaVar, const std::map<int, int> &varConMap,
290 int &varIdx, int &numNonz, int* &indexes, double* &values) ;
291
292
302 int getBranchingVar(const double* theta, const int numThetaVar ) ;
303
304
317 int getBranchingVar(const int* thetaIdx, const double* theta, const int numThetaVar ) ;
318
319
333 virtual void getColumns(const double* yA, const int numARows,
334 const double* yB, const int numBRows,
335 int &numNewColumns, int* &numNonz, double* &cost,
336 int** &rowIdx, double** &values, double &lowerBound) ;
337
338
339
340
341
343
344
345 //some utility methods are below
346
353 void calcReducedCost(const double* yA, const double* yB );
354
355 //these are the variable in x(i, j) space
356 void createVariableNames( );
357
358 //this is the matrix that says we must visit each node
359 //this A matrix defines the "coupling constraints"
360 void createAmatrix();
361
365 virtual void initializeDataStructures();
366
370 void getInitialSolution();
371
372 virtual void resetMaster( std::map<int, int> &inVars,
373 OsiSolverInterface *si );
374
375 //this method gets called when we are done
376 virtual void pauHana(std::vector<int> &m_zOptIndexes , int numNodes,
377 int numColsGen);
378
379
395 void getCutsMultiCommod(const double* thetaVar, const int numThetaVar,
396 int &numNewRows, int* &numNonz, int** &colIdx,
397 double** &values, double* &rowLB, double* &rowUB) ;
398
399
400
406
412
413
419
420
421 class Factory;
423
424 public:
425
427
428 }
429
431
432 }
433
435
436 };// end class OSDipBlockSolverFactory
437
438
439};//end class OSBearcatSolverXkij
440
441#endif
442
OSOption * osoption
OSInstance * getSeparationInstance()
virtual OSInstance * getInitialRestrictedMaster()
OSInstance* OSBearcatSolverXkij::getInitialRestrictedMaster( ){.
int * m_routeCapacity
the route capacity – bus seating limit this can vary with the route/hub
virtual void resetMaster(std::map< int, int > &inVars, OsiSolverInterface *si)
INPUT:
double qrouteCost(const int &k, const int &l, const double *c, int *kountVar)
kipp – document
OSInstance * m_osinstanceSeparation
int * m_upperBoundL
largest possible L-value on a route – this will be the minimum of m_routeCapacity and total demand
double ** m_rc
the reduced cost vector for each k, we asssume order is (l, i, j)
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.
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...
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...
int m_minDemand
m_minDemand is the value of the minimum demand node – it is not the minimum demand that must be carri...
int * convexityRowIndex
conconvexityRowIndex holds the index of the convexity row that the theta columns are in.
void getOptions(OSOption *osoption)
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...
~OSBearcatSolverXkij()
Default Destructor.
int * m_routeMinPickup
the minimum number of students that we pickup on a route this can vary with the route/hub
OSBearcatSolverXkij()
Default Constructor.
void getInitialSolution()
generate an intitial feasible solution in theta space for the initial master
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...
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...
int * m_separationIndexMap
m_separationIndexMap maps the variable index into the appropriate row in the separation problem for t...
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...
virtual void pauHana(std::vector< int > &m_zOptIndexes, int numNodes, int numColsGen)
int * m_lowerBoundL
smallest possible L-value on a route for now this will equal
ClpSimplex * m_separationClpModel
int * m_demand
m_demand is the vector of node demands
virtual void initializeDataStructures()
allocate memory and initialize arrays
int m_maxThetaNonz
m_maxMasterNonz is the maximumn number of nonzero elements we allow in the transformation matrix betw...
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 ...
int getBranchingVar(const double *theta, const int numThetaVar)
RETURN VALUES: return the integer index of a fractional x_{ij} variable.
int m_upperBoundLMax
largest possible L-value over all routes
double ** m_cost
the distance/cost vectors
The in-memory representation of an OSiL instance..
The Option Class.
Definition OSOption.h:3565