This repository contains a Java implementation of a Benders Decomposition algorithm to solve the Directed Robust Perfect b-Matching Problem (DRPbM).
The project was developed as part of a computational study on decomposition-based optimization methods for two-stage robust optimization problems.
The results are part of my PhD-thesis and will be published in the near future.
The Directed Robust Perfect b-Matching Problem (DRPbM) is a combinatorial optimization problem that extends the classical b-matching formulation to directed graphs with robustness considerations against uncertainty in the capacity.
The formal definition and theoretical background of the problem are presented in:
Jenny Segschneider, Arie M.C.A. Koster (2025).
Complexity of the Directed Robust b-Matching Problem and Its Variants on Different Graph Classes
Networks, 86(2), 220–237.
https://onlinelibrary.wiley.com/doi/10.1002/net.22286
This project implements and extends a Benders Decomposition approach for solving DRPbM instances efficiently, integrating several speed-up techniques and computational enhancements as discussed in The Benders decomposition algorithm: A literature review by Ragheb Rahmaniani et al.
- Exact Benders Decomposition Framework
- Master and subproblem separation
- Cut generation and management
- Speed-up Techniques as discussed by Ragheb Rahmaniani et al. and adapted to DRPbM.
- Decomposition Strategies
- Partial Benders Decomposition
- Solution Generation
- Two-Phase Approach by McDaniel and Devine
- Cut Generaton
- adding Benders Cuts for non-integer solutions found, either only in the root node or always
- generating (nearly) Pareto-optimal cuts using the approach by Magnanti and Wong, and its improved variant proposed by Papadakos
- generating cuts from a minimum infeasible subsystem
- Solution Procedure in the Benders Main Problem
- Using valid inequalities for b-matchings to cut off non-integer solutions by separation (requires Partial Benders Decomposition)
- Using valid inequalities for pre-matchings to cut off non-integer solutions by separation
- Solution Procedure in the Subproblem
- Parallel Computing
- alternative subproblem formulation
- only consider a subset of all subproblems each iteration using a solling horizon approach
- adaptive scenario aggregation as proposed by Ramírez-Pico, Ljubi¢, and Moreno
- Decomposition Strategies
- Modular and Extensible Java Codebase
- Clear separation of model, solver, and utility layers
- Benchmarking Framework
- Automatic instance generation and logging
- CSV-based output for statistical analysis
src/
├── data/
│ └── InstanceGenerator.java
├── datenstructure/
│ ├── myEdgeSupplier.java
│ ├── myVertexSupplier.java
│ ├── RobustBMatching.java
│ ├── RobustMatchingGraph.java
│ ├── Run.java
│ └── Subproblem.java
└── statistics/
└── RunExperiment.java
└── Main.java
- Java 17 or higher
- Gurobi for MILP solving (requires a license)
Clone the repository:
git clone https://github.com/JennySegschneider/DirectedRobustBMatchingBendersDecomposition.gitChoose instances and Speed-up techniques:
All Settings for the computation as well as the generation and instance size can be set in config.json. In the file, the first block of entries corresponds to general setting: if a perfect b-matching or a regular b-matching should be solved, which algorithms should be used and the runtime limit for all computations. The second block corresponds to the settings and speed-up techniques for the Benders Decomposition algorithm. The third block includes details about the instance generation. A detailed explanation of all settings can be found below.
Compile and run using maven:
mvn clean install
java -jar target/DirectedRobustBMatchingBendersDecomposition-1.0-SNAPSHOT.jarResults are written to output_runs/runx/quick_info as CSV, all logs and details for each instance are saved in the same folder.
The file config.json includes all settings and configuration for the study, including general run settings, settings for speed-up techniques, and settings for the instance generation. Here, I will quickly go over the settings and what they do. The displayed settings are used for the standard implementation of the Benders decomposition in the computational study.
"perfect": true, "useMIP": true, "useBenders": true, "runtimeLimit": 600,
The boolean perfect sets the problem itself: if it is set to true, a perfect b-matching problem is solved. Else, a 'regular', not necessarily perfect, b-matching problem is solved. The two booleans useMIP and useBenders decide which algorithms are used. If useMIP is set to true, the problem is solved by solving an MIP formulation with Gurobi. The same holds for useBenders. If both are set to true, both algorithms are used to solve each instance. The runtimeLimit applies an upper limit for the runtime of each single instance and solving of that instance is stopped if the limit is reached.
The next section includes settings for the Benders decomposition and its speed-up techniques.
"algFeas": "None", "algOpt": "Gurobi_Both_Separate_Scenarios",
These set the algorithms used to compute the Benders cuts. algFeas is only used if the feasibility cuts are generated separately from the optimality cuts. Options include using parallel computing, finding a minimum infeasible subsystem, and an adaptive scenarios aggregation. See Subproblem.java for details regarding supportes algorithms.
"numScenariosCutGeneration": null,
This sets the number of scenarios for which Benders Cuts are generated in each iteration. The scenarios are picked using a Round Robin principle.
"noFeasCutsAfter": null,
Stop generating feasibility cuts after a certain amount of iterations without new feasibility cuts. This only works if feasibility and optimality cuts are generated separately and may lead to an infeasibly solution!
"usePMConstraintsInBendersMain": true,
Include additional valid inequalities on the pre-matching variables in the Benders Main.
"numScenariosInBendersMain": 0, "methodChoosingScenariosForBendersMain": "None",
These two settings are used for the Partial Benders Decomposition. The first one dictates how many scenarios are included in the Benders Main, the second one sets which scenarios are chosen. See RobustBMatching for details on the algorithms.
"removeDominatedCuts": false, "liftCuts": false,
These were only used for theoretical insights and not computational performance. If the first setting is set to true, trivially dominated cuts are removed in each iteration. Since Gurobi does this automatically, this step is only helpful when looking at the cuts by hand. If the second setting is true, all generated cuts are lifted by finding the maximum feasible right-hand-side. This is done by maximizing the left-hand-side over all feasible solutions in the (current) Benders Main and thus, very inefficient.
"cutNonIntSolutions": false, "cutNonIntInRoot": false, "cutSeparationIntSolution": "None",
These settings dictate if and how fractional solutions are cut off. If the first is set to true, we try to cut off fractional solutions with regular Benders Cuts. If the second setting is also true, we only do this while the Branch&Bound tree is still in its root node. Finally, the third setting picks the algorithm used to separate fractional solutions using valid inequalities. See RobustBMatching for details on the available algorithms.
"paretoOtimalOptCuts": "None", "corePointAlg": "None",
These settings are used to generate (nearly) pareto-optimal cuts. The first option sets the algorithm to find better cuts, where the option Minimize_Dual_Variable finds a Benders Cuts where the dual variables have minimal value and the option Nearly_Pareto_Optimal uses the approach by Magnanti and Wong. For this approach, the needed Core Point is generated using the algorithm specified by corePointAlg. Refer to RobustBMatching.java for details on the available algorithms.
"cutAggregationMethod": "None",
Adaptively aggregate the cuts of different scenarios before adding them to the Benders Main in each iteration. This requires "algOpt": "Gurobi_Both_Single_Cut_Partition". See Subprobem.java for details on the available algorithms.
"numberCutsNonstandardDecomposition": 0,
For the nonstandard decomposition, this sets the number of cuts generated after which the second phase starts.
The next settings only influence the instance generation:
"instances": "RandomGraphGenerator", "numberInstances": 100, "startAtInstance": 0, "numScnearios": 50, "minNumVertex": 50, "maxNumVertex": 50, "minFactorArc": 2, "maxFactorArc": 2, "minFactorCapacities": 10, "maxFactorCapacities": 10, "integerCapacities": true, "seed": 2024
Instances are generated using the algorithm specified in the first setting. The seed for each instance is the number of the instance, i.e., instance 1 uses seed 1 and so on. For solving a specific instance, i.e., instance 10, the setting startAtInstance can be used. For the random graphs, the number of vertices is randomly generated between minNumVertex and maxNumVertex. If both values are the same, there is no random choice. The number of arcs and the sum of the capacity is randomly chosen the same way, but expressed related to the number of vertices. For a given FactorArc, the graph gets FactorArc times NumVertex arcs. The same holds for the capacities. Finally, integerCapacities is set to true if all capacities are supposed to be integer and seed sets the seed for all non-instance randomization and computations.
This is an example output of a computation using both algorithms including explanation of the data points.
Run;1 # Runtime in seconds when solving the MIP formulation directly compared to the Benders decomposition, includes pre-processing and building of the model Run_time_sec_MIP; 9.2 7.1 ... Run_time_sec_Benders; 4.9 2.6 ... # Runtime in seconds used to solve the model with Gurobi, excludes some pre-processing and building of the model Run_time_MIP_Grb; 4.5 3.8 ... Run_time_Benders_Grb; 3.8 2.1 ... # objective value of the optimal solution, should be the same for both approaches Opt_Val_MIP; 4267.0 4317.0 ... Opt_Val_Benders_Grb; 4267.0 4317.0 ... # Number of Feasibility, Optimiality, and Integer Cuts generated in the Benders decomposition Feas_Cuts; 25.0 14.0 ... Opt_Cuts; 1 0 ... Int_Cuts; 0 0 ... # Time spent in the callback (solving the subproblem) and number of callbacks in the Benders decomposition Time_CB; 3.9 2.2 ... Number_CB; 4.0 4.0 ... # Number of nodes of the Branch and Bound Tree from Gurobi Number_Nodes_MIP; 1.0 1.0 ... Number_Nodes_Benders; 99.0 1.0 ...
Jenny Segschneider
📧 segschneider@math2.rwth-aachen.com
💼 Website
If you use this code or build upon it, please cite:
@misc{segschneider2025drpbm,
author = {Jenny Segschneider},
title = {Benders Decomposition for the Directed Robust Perfect b-Matching Problem},
year = {2025},
howpublished = {\url{https://github.com/JennySegschneider/DirectedRobustBMatchingBendersDecomposition.git}}
}