main_vrp.cpp File Reference

Detailed Description

main file for VRP pricer example

Author

Andreas Bley

Marc Pfetsch

We want to solve the vehicle routing problem on a graph \(G = (V,E)\) with \(V = J \cup \{d\}\), where d is the depot and the distances are given by the length function \(l_e: E \rightarrow R_{\geq 0}\).

Consider the MIP formulation

\[ \begin{array}[t]{rll} \min & \displaystyle \sum_{e \in E} l_e y_e \\ & & \\ s.t. & -y_e + \sum_{t \in T_k} a^t_e x_t \leq 0, & \forall e \in E\\ & \displaystyle \sum_{t \in T_k} a^t_j x_t = 1, & \forall j \in J \\ & y(\delta(j)) = 2, & \forall j \in J \\ & y_e \in \{0,1,2\}, & \forall e \in E \\ & x_t \in [0,1], & \forall t \in T_k \end{array} \]

where \(T_k\) is the set of tours visiting at most k customers with repetitions of customers allowed and \(a^t_e\) ( \(a^t_j\)) counts how often edge e (node j) is traversed in \(t \in T_k\).

Examples and the file format are given at https://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/.

Definition in file main_vrp.cpp.

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include "objscip/objscip.h"
#include "objscip/objscipdefplugins.h"
#include "pricer_vrp.h"

Go to the source code of this file.

Functions
static int	read_problem (const char *filename, int &num_nodes, int &capacity, vector< int > &demand, vector< vector< int > > &dist)
static SCIP_RETCODE	execmain (int argc, char **argv)
int	main (int argc, char **argv)

Function Documentation

read_problem()

static int read_problem ( const char *  filename, int &  num_nodes, int &  capacity, vector< int > &  demand, vector< vector< int > > &  dist  )

static

read VRP problem

Parameters

filename	filename
num_nodes	number of nodes in instance
capacity	capacity in instance
demand	array of demands of instance
dist	distances between nodes

Definition at line 77 of file main_vrp.cpp.

References x, and y.

Referenced by execmain().

execmain()

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

static

Definition at line 246 of file main_vrp.cpp.

References BMScheckEmptyMemory, FALSE, NULL, read_problem(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PARAMETERUNKNOWN, SCIP_READERROR, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPactivatePricer(), SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPcreate(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPfindPricer(), SCIPfree(), SCIPincludeDefaultPlugins(), SCIPincludeObjPricer(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintBestSol(), SCIPprintStatistics(), SCIPprintVersion(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetIntParam(), SCIPsnprintf(), and SCIPsolve().

Referenced by main().

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 493 of file main_vrp.cpp.

References execmain(), and SCIP_OKAY.