#include <TSP_DecompApp.h>
Public Member Functions | |
virtual DecompSolverStatus | solveRelaxed (const int whichBlock, const double *redCostX, const double convexDual, DecompVarList &varList) |
Solve the relaxed problem. | |
virtual int | generateCuts (const double *x, DecompCutList &newCuts) |
Initialize the dual vector for PhaseII of PC. | |
virtual bool | APPisUserFeasible (const double *x, const int n_cols, const double tolZero) |
Method to determine if the solution (x) is feasible to the original model. | |
virtual void | printOriginalColumn (const int index, ostream *os) const |
Constructor and Destructor | |
TSP_DecompApp (UtilParameters &utilParam) | |
Default constructor. | |
virtual | ~TSP_DecompApp () |
Default constructor. | |
Private Member Functions | |
Helper functions (private). | |
void | initializeApp (UtilParameters &utilParam) |
Guts of constructor. | |
void | createModels () |
Create models. | |
void | createModel2Match (DecompConstraintSet *modelCS) |
Create the two-matching constraints. | |
void | createModelTrivialSEC (DecompConstraintSet *modelCS) |
Create trivial subtour elimination constraints. | |
int | generateCutsSubtour (DecompCutList &newCuts) |
Guts of constructor. | |
void | solveOneTree (const double *cost, const double alpha, vector< pair< int, double > > &edge_cost, DecompVarList &vars, Graph &g) |
Guts of constructor. | |
Private Attributes | |
const string | m_classTag |
Class id tag (for log / debugging). | |
TSP_Param | m_appParam |
Application specific parameters. | |
TSP_Instance | m_tsp |
Storage of TSP instance. | |
double * | m_objective |
The model objective coefficients (original space). | |
vector< DecompConstraintSet * > | m_models |
The various model constraint systems used for different algos. |
A DecompApp for solving the Traveling Salesman Problem.
Definition at line 33 of file TSP_DecompApp.h.
TSP_DecompApp::TSP_DecompApp | ( | UtilParameters & | utilParam | ) | [inline] |
Default constructor.
Takes an instance of UtilParameters
Definition at line 96 of file TSP_DecompApp.h.
References initializeApp().
virtual TSP_DecompApp::~TSP_DecompApp | ( | ) | [inline, virtual] |
Default constructor.
Takes an instance of UtilParameters
Definition at line 104 of file TSP_DecompApp.h.
References m_models, m_objective, UTIL_DELARR, and UtilDeleteVectorPtr().
virtual DecompSolverStatus TSP_DecompApp::solveRelaxed | ( | const int | whichBlock, | |
const double * | redCostX, | |||
const double | convexDual, | |||
DecompVarList & | varList | |||
) | [virtual] |
Solve the relaxed problem.
Reimplemented from DecompApp.
virtual int TSP_DecompApp::generateCuts | ( | const double * | x, | |
DecompCutList & | newCuts | |||
) | [virtual] |
Initialize the dual vector for PhaseII of PC.
The user is passed a reference to the internal data and can manipulate it directly.
This is only called when dual stabilization is used, i.e., when m_param.DualStab > 0, at the first iteration of PhaseII of PC. The vector is immediately smoothed with the initial restricted master duals. By default, the restricted mater is used as the initial dual and, therefore, no smoothing occurs in the first iteration.
Reimplemented from DecompApp.
virtual bool TSP_DecompApp::APPisUserFeasible | ( | const double * | x, | |
const int | numCols, | |||
const double | tolZero | |||
) | [virtual] |
Method to determine if the solution (x) is feasible to the original model.
For explicitly defined model components, like the model core constraints (A''), the feasibility of the solution is automatically checked against the constraints. In the case when the relaxed problem constraints (A') are explicitly defined - these are also checked automatically.
However, for some applications, a valid feasible constraint system cannot be explicitly defined (even for the core set of constraints). For example, think of the case of TSP, where A'' is defined as the subtour elimination constraints. These constraints are implicitly defined by deriving the method DecompApp::generateCuts. Therefore, the framework cannot automatically tell if a solution is feasible by checking against the constraint system. In this case, the user must provide this method.
[in] | x | The solution point to check. |
Reimplemented from DecompApp.
virtual void TSP_DecompApp::printOriginalColumn | ( | const int | index, | |
ostream * | os | |||
) | const [virtual] |
Reimplemented from DecompApp.
void TSP_DecompApp::initializeApp | ( | UtilParameters & | utilParam | ) | [private, virtual] |
void TSP_DecompApp::createModels | ( | ) | [private] |
Create models.
Reimplemented from DecompApp.
void TSP_DecompApp::createModel2Match | ( | DecompConstraintSet * | modelCS | ) | [private] |
Create the two-matching constraints.
void TSP_DecompApp::createModelTrivialSEC | ( | DecompConstraintSet * | modelCS | ) | [private] |
Create trivial subtour elimination constraints.
int TSP_DecompApp::generateCutsSubtour | ( | DecompCutList & | newCuts | ) | [private] |
Guts of constructor.
void TSP_DecompApp::solveOneTree | ( | const double * | cost, | |
const double | alpha, | |||
vector< pair< int, double > > & | edge_cost, | |||
DecompVarList & | vars, | |||
Graph & | g | |||
) | [private] |
Guts of constructor.
const string TSP_DecompApp::m_classTag [private] |
Class id tag (for log / debugging).
Reimplemented from DecompApp.
Definition at line 36 of file TSP_DecompApp.h.
TSP_Param TSP_DecompApp::m_appParam [private] |
Application specific parameters.
Definition at line 39 of file TSP_DecompApp.h.
TSP_Instance TSP_DecompApp::m_tsp [private] |
Storage of TSP instance.
Definition at line 42 of file TSP_DecompApp.h.
double* TSP_DecompApp::m_objective [private] |
The model objective coefficients (original space).
Reimplemented from DecompApp.
Definition at line 45 of file TSP_DecompApp.h.
Referenced by ~TSP_DecompApp().
vector<DecompConstraintSet*> TSP_DecompApp::m_models [private] |
The various model constraint systems used for different algos.
Definition at line 48 of file TSP_DecompApp.h.
Referenced by ~TSP_DecompApp().