 # SCIP

Solving Constraint Integer Programs

 Main Page Data Structures Files xternal.c Go to the documentation of this file. 1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15  16 /**@file xternal.c 17  * @brief main document page of VRP example 18  * @author Andreas Bley 19  */ 20  21 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 22  23 /**@mainpage Overview 24  * @version 0.1 25  * @author Andreas Bley 26  * 27  * 28  * We want to solve the vehicle routing problem (VRP) on a graph \f$G = (V,E)\f$ with 29  * \f$V = J \cup {d}\f$, where \f$d\f$ is the depot and the distances are given by the 30  * length function \f$l_e: E \to R_{\ge 0}\f$. 31  * 32  * Consider the MIP formulation 33  * 34  * \f[ 35  * \begin{array}[t]{rll} 36  * \min & \displaystyle \sum_{e \in E} l_e y_e \\ 37  * & & \\ 38  * s.t. & -y_e + \sum_{t \in T_k} a^t_e x_t \leq 0, & \forall e \in E\\ 39  * & \displaystyle \sum_{t \in T_k} a^t_j x_t = 1, & \forall j \in J \\ 40  * & y(\delta(j)) = 2, & \forall j \in J \\ 41  * & y_e \in \{0,1,2\}, & \forall e \in E \\ 42  * & x_t \in [0,1], & \forall t \in T_k 43  * \end{array} 44  * \f] 45  * 46  * where \f$T_k\f$ is the set of tours visiting at most \f$k\f$ customers 47  * with repetitions of customers allowed and \f$a^t_e (a^t_j)\f$ counts how often 48  * edge e (node j) is traversed in \f$t \in T_k\f$. 49  */ 50  Generated on Wed Apr 2 2014 for VRP Example (Branch-and-Price) by doxygen (1.8.2) © 2021 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap