cppmain.cpp File Reference

Detailed Description

main file for C++ TSP example using SCIP as a callable library

Author

Tobias Achterberg

Timo Berthold

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:

1. sum_{e in delta(v)} x_e == 2 for all v in V
2. subtour(G,x)

Semantics of constraints:

1. usual linear constraints
2. subtour(G,x) <=> T defined by x does not contain any cycle of length < |V|

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

1. A pointer to each variable is stored in the data structure of the corresponding edge (i.e., in edge->var and edge->back->var, since the formally undirected graph is represented as a directed graph with antiparallel arcs). The degree constraints are created at line 330. The data for the linear degree constraints are the coefficients (for each e in delta(v) the variable x_e has coefficient 1.0) which are generated at line 337, and the left and right hand sides of the inequality, which are both set to 2.0 at line 330, such that the linear constraint becomes an equation. The subtour constraint is created at line 349. The data for this constraint is the graph and the variables (see above), but we only have to store a pointer to the graph because the edges already have links to their respective variables.

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)

Function Documentation

runSCIP()

static SCIP_RETCODE runSCIP ( int  argc, char **  argv  )

static

creates and runs a SCIP instance with default and TSP plugins

Parameters

argc	number of arguments from the shell
argv	array of shell arguments

Definition at line 105 of file cppmain.cpp.

References BMScheckEmptyMemory, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPenableDebugSol(), SCIPfree(), SCIPincludeDefaultPlugins(), SCIPincludeObjConshdlr(), SCIPincludeObjEventhdlr(), SCIPincludeObjHeur(), SCIPincludeObjReader(), SCIPprocessShellArguments(), and TRUE.

Referenced by main().

main()

int main	(	int	argc,
		char **	argv
	)

main method starting TSP code

Parameters

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().