main file for C++ TSP example using SCIP as a callable library
This is an example of using SCIP to solve the TSP problem on undirected graphs. Here is the CIP model that we use:
Given: a graph G=(V,E) with edge weights c_e Task: find hamiltonian cycle T subseteq E in G with minimal length c(T)
Variables: x_e in {0,1} for all e in E, x_e = 1 <=> e in T Constraints:
Semantics of constraints:
A few remarks to the model and the implementation (references to code lines might not be up to date):
As one can see, the TSP-Model consists of |V| linear constraints (the degree constraints) and one "subtour" constraint. The latter is a complex, non-linear constraint for which one has to implement an own constraint handler. The variables are created in the TSP file reader ReaderTsp.cpp at line
Now the problem instance is defined, and the "only" thing left is to implement the semantics of the "subtour" constraint. This is of course done in the subtour constraint handler ConshdlrSubtour.cpp. The main task of a constraint handler is to decide whether a given solution is feasible for all constraints of the constraint handler's type (i.e., for example, for all linear constraint in the instance, for all knapsack constraints in the instance, for all subtour constraints in the instance, ...). This is performed in the scip_enfolp(), scip_enfops(), and scip_check() methods. To implement these three methods and the scip_lock() method (called the "fundamental callback methods" in the SCIP documentation) is already enough to obtain a correct algorithm, which means that the solver will find (after waiting long enough) the optimal solution. The remaining methods are only needed to speed up the solving process (for example, cutting plane separation and domain propagation).
As there is only one subtour constraint in a TSP instance, all the loops "for( int i = 0; i < nconss; ++i )" in ConshdlrSubtour.cpp are a bit ridiculous, since nconss will always be equal to one. However, nothing prevents a user from using the subtour constraint handler in a different application where you have more than one graph and a solution must not contain any subtour in each of the graphs.
Definition in file cppmain.cpp.
#include <iostream>
#include "objscip/objscip.h"
#include "objscip/objscipdefplugins.h"
#include "ReaderTSP.h"
#include "ConshdlrSubtour.h"
#include "HeurFarthestInsert.h"
#include "Heur2opt.h"
#include "HeurFrats.h"
#include "EventhdlrNewSol.h"
Go to the source code of this file.
Functions | |
static SCIP_RETCODE | runSCIP (int argc, char **argv) |
int | main (int argc, char **argv) |
|
static |
creates and runs a SCIP instance with default and TSP plugins
argc | number of arguments from the shell |
argv | array of shell arguments |
Definition at line 105 of file cppmain.cpp.
References BMScheckEmptyMemory, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPenableDebugSol(), SCIPfree(), SCIPincludeDefaultPlugins(), SCIPincludeObjConshdlr(), SCIPincludeObjEventhdlr(), SCIPincludeObjHeur(), SCIPincludeObjReader(), SCIPprocessShellArguments(), and TRUE.
Referenced by main().
int main | ( | int | argc, |
char ** | argv | ||
) |
main method starting TSP code
argc | number of arguments from the shell |
argv | array of shell arguments |
Definition at line 154 of file cppmain.cpp.
References runSCIP(), SCIP_OKAY, and SCIPprintError().