A Vertex-Based Solver for Steiner Multigraph Problem

A novel and efficient Branch-and-Cut based solver integrating with hybrid heuristics for Steiner Multigraph Problem (SMP) 👏💖. Our algorithms/solver are able to solve large instances of more than ten thousands vertices in less than one hour.

The code also includes implementation of the Single-Commodity Flow (SCF), Multi-Commodity Flow (MCF) and Steiner Forest (SF) Model used for comparison and analysis.

Differences between three Git branches:

• master: a high level implementation, which should only be used as understanding of the code.
• ThomasLB: implementing the separation by the Lemon Graph Library. Can be fully complied and run.
• ThomasLC: implementing the separation without applying external tools but by self-dedicated snippets codes. Can be fully complied and run.

Preparations

The original code is guaranteed to be complied and executed only on Windows 10 yet (not tested on other OS).

Follow the necessary steps below to make it run 😊:

1. Install Visual Studio 2017;
2. Download CPLEX 12.7.1;
3. Download Lemon Graph Library;
4. Follow the User Manual for CPLEX and Install Instruction for Lemon to install both assistant tools and make it compact to Visual Studio 2017.

Compile and Run

1. To compile, select Build->Build Solution (or press F7) on main bar of Visual Studio 2017's coding window.

2. To run .exe file, the command line can be changed arbitrarily but should contain following indexes:

   $ exeAbsltLocation, tempDataLocation, formulation, callback_option, relax_option, 
   ns_sep_opt, LB_MaxRestart, LB_MaxIter, Rmin, Rmax, BCSolNum, BCTime, MIPDisplayLevel, 
   TimeLimit, MaxCutNumberLazy, epsilonLazy, MaxCutNumberUser, epsilonUser, UseLocalBranch, 
   LP_CP_Option, LazySepOpt
   

   Explanation of the parameters:

   Parameter Name	Usage
   exeAbsltLocation	Absolute path of executable .exe file
   tempDataLocation	Data location
   formulation	Which formulation would like run, 1: SCF, 2:MCF, 3:SF, 4:NS
   callback_option	Add callkack for SF and NS: 1 use only LZ , 2: use only User 3: both LZ and User
   relax_option	Solving MIP with relaxation, 1: Yes, 0: No
   ns_sep_opt	When row generation for User Cut finished, 1: check the feasibility of Cut using LZ separation, 0: not do so
   LB_MaxRestart	Valid only when Local Search applied, control the maximum number of search restart
   LB_MaxIter	Valid only when Local Search applied, control the maximum number of iteration using same initial solution
   Rmin	Valid only when Local Search applied, minimum of search radius in feasible region
   Rmax	Valid only when Local Search applied, maximum of search radius in feasible region
   BCSolNum	Valid only when Local Search applied, maximum solution number can be found in B&C in one iteration
   BCTime	Valid only when Local Search applied, maximum solving time in B&C in one iteration
   MIPDisplayLevel	Control the display level for CPLEX
   TimeLimit	Time limit for running the solver
   MaxCutNumberLazy	Maximum number of cut added in Lazy separation finished
   epsilonLazy	The error threshold for the cut generated by Lazy separation
   MaxCutNumberUser	Maximum number of cut added in User separation finished
   epsilonUser	The error threshold for the cut generated by User separation
   UseLocalBranch	1: Use Local Branch globally, 0: not
   LP_CP_Option	1: Use Cut pool, add violation constraint as cut in LB stage, 0: do not use cut pool add violation as constraint
   LazySepOpt	In LZ separation, 1: generate cut between all pairs of SCC, 0: generate cut between only first SCC and others

Contents in each file

Following table summarizes the major contents in each file:

File Name	Contents
main.cpp	The entry of the code. Parser the input command and initialize the raw model.
readers.cpp	Used for loading the data, meanwhile check whether the graph is legal (optional).
type.h	Defines all customized type and variables alias.
graph.h	Defines the graph structure used in solver.
unionfind.h	Implementation of Union-Find algorithm.
smp.h	Head file for smp.cpp, defines the general solver class and the one integrating Local Branch .
smp.cpp	Implementation of 4 different algorithms and set all necessary parameters for CPLEX.
seperation.h	Head file for seperaion.cpp. Defines function format and necessary parameters.
seperation.cpp	Implementation of SCC and Min-cut separation for SF and NS model.
callback.h	Defines the interactive callback option for SF and NS in CPLEX.

Instance Format

The input graph should be constructed by following steps simutaneously:

1. First line contains the nodes number N, following N lines each line has a pair of numbers (u,cost) indicates the cost associate to node u.
2. After that, a number M which is the edge number and following M lines each line has a nodes pair (u,v) indicates there is a edge between u and v.
3. A partition number P, followed by P different each partition blocks, each block start with a integer n represents the nodes number in p and list of the index of these nodes, another integer T indicates the number of terminals followed by T different nodes index as well.

Ciatation

If you use our code, please cite our paper:

@article{ma2023vertex,
  title={A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem},
  author={Ma, Mengfan and Men, Ziyang and Rossi, Andr{\'e} and Zhou, Yi and Xiao, Mingyu},
  journal={Computers \& Operations Research},
  volume={153},
  pages={106151},
  year={2023},
  publisher={Elsevier}
}