Running DD-suite

DD-suite includes three main files (i.e., programs) to run all the basic features provided by the tool over the five discrete optimization problems that we provide as examples (i.e., Knapsack, Independent Set, Set Cover, SOC Knapsack, and Sequencing). Specifically, we offer the following three programs:

main: creates a DD for the problem
main_gurobi: solves the problem using a MILP and the Gurobi solver
main_cuts: solve the problem using our cutting plane implementation in Gurobi with DD-base cuts

In general, the user has to employ the following syntax to run the selected program from the command line:

PythonC++

python3 ./program_name.py [filename] [flags]

./program_name [filename] [flags]

Here, program_name can be either main, main_gurobi or main_cuts. The parameters are:

filename: The input file containing problem data. See Input Data for more details.
flags: Optional flags to specify the problem class, DD type, and other options.

We note that these three programs are provided as examples of how to use DD-suite. Users can freely modify these main files or create new ones according to their specific requirements.

Error Handling

All programs must specify a valid problem class (i.e., use flags -SetCover, -Knapsack, -IndependentSet, -SOCKnapsack, or -Sequencing). Otherwise, the program will display the following error message:

Error: A valid problem class was not specified.

All other flags are optional and have default values as specified below.

Input Data

DD-suite includes input data for the five problem classes in the DataInstances folder, with one folder per problem class (Knapsack, IndependentSet, SetCover, SOCKnapsack, Sequencing). Inside each one, Standard holds the benchmark instances taken from the literature and Custom the randomly generated ones (SOCKnapsack only has Standard). Both are already converted to the format the programs read, so files from either folder can be passed directly; the conversion scripts live in each problem's Instances_generation folder. As an example, a valid input data for main with the -SetCover flag is:

DataInstances/SetCover/Custom/set_cover_v6_r3_seed1.txt

Running main

In this program, you can create any of the three DD types (e.g., Exact, Restricted, and Relaxed), then reduce it, export it, and/or obtain the path with minimum/maximum length. Additionally, all this information, along with execution times, can be saved in an output file specified via the command line.

Command-Line Flags

Below is a list of available flags and their descriptions:

Flag	Description
`-SetCover`	Specifies the problem class as Set Cover
`-Knapsack`	Specifies the problem class as Knapsack
`-IndependentSet`	Specifies the problem class as Independent Set
`-SOCKnapsack`	Specifies the problem class as SOC Knapsack
`-Sequencing`	Specifies the problem class as Sequencing
`-Exact`	Specifies the DD type as Exact
`-Restricted`	Specifies the DD type as Restricted
`-RelaxPriority`	Specifies the DD type as Relaxed (merge nodes by priority)
`-RelaxGrouping`	Specifies the DD type as Relaxed (merge nodes in groups by priority difference)
`-Width_`	Sets the maximum width for Restricted/Relaxed DD (e.g. `-Width_100`)
`-Reduce`	Enables reduction of the DD
`-Verbose`	Enables verbose mode for detailed output
`-Export`	Enables export of the DD
`-Max`	Computes the longest path (default is shortest path)
`-Min`	Computes the shortest path
`-NoSort`	Keeps the original variable order (disables sorting heuristic)
`-Output_`	Specifies the output file path (e.g. `-Output_result.txt`)

Execution Example

PythonC++

python3 ./main.py example_input.txt -SetCover -RelaxPriority -Width_100 -Reduce -Verbose -Output_result.txt

./main example_input.txt -SetCover -RelaxPriority -Width_100 -Reduce -Verbose -Output_result.txt

Output Example

When the program runs, it displays the following information:

Running with the following parameters:
Input File: example_input.txt
Output File: result.txt
Problem Class: Set Cover
DD Type: RelaxPriority
Maximum Width: 100
Reduce: Yes
Verbose: Yes
Export: No
Min/Max?: min
Sort: Yes

Notes

The program automatically determines the current directory and appends it to the input and output file paths to ensure all necessary files are correctly located.
Default values are used for unspecified parameters (e.g., DD type defaults to Exact, and maximum width defaults to 2147483646, i.e. effectively unbounded).
If the -Output_ flag is omitted, no output file will be generated.

Running main_gurobi

This executable creates a Gurobi optimization model for any of the supported problem classes: Set Cover, Knapsack, Independent Set, SOC Knapsack, and Sequencing. Additionally, all the information, including execution times, can be saved to an output file specified via the command line.

Command-Line Flags

Below is a list of available flags and their descriptions:

Flag	Description
`-SetCover`	Specifies the problem class as Set Cover
`-Knapsack`	Specifies the problem class as Knapsack
`-IndependentSet`	Specifies the problem class as Independent Set
`-SOCKnapsack`	Specifies the problem class as SOC Knapsack
`-Sequencing`	Specifies the problem class as Sequencing
`-Verbose`	Enables verbose mode for detailed output
`-Continuous`	Uses continuous variables instead of integer variables
`-Output_`	Specifies the output file path

Execution Example

Here is an example command to run the program:

PythonC++

python3 ./main_gurobi.py example_input.txt -SetCover -Verbose -Output_solution.txt

./main_gurobi example_input.txt -SetCover -Verbose -Output_solution.txt

Output Example

When the program runs, it displays the following information:

Running with the following parameters:
Input File: example_input.txt
Output File: solution.txt
Problem Class: Set Cover
Verbose: Yes
Continuous: No

Notes

The program automatically determines the current directory and appends it to the input and output file paths to ensure all necessary files are correctly located.
Default behavior uses integer variables unless the -Continuous flag is provided.
If the -Output_ flag is omitted, no output file will be generated.

Running main_cuts

This program runs the DD-based cutting plane approach described in our paper (See Reference). Specifically, it solves a discrete optimization problem using a simple cutting plane implementation using Gurobi, where we generate (and strengthen) DD-based cuts (i.e., Flow Cuts, JointFlow Cuts, or Target Cuts). In addition, all this information, along with execution times, can be saved in an output file specified via the command line.

Command-Line Flags

Below is a list of available flags and their descriptions:

Flag	Description
`-SetCover`	Specifies the problem class as Set Cover
`-Knapsack`	Specifies the problem class as Knapsack
`-IndependentSet`	Specifies the problem class as Independent Set
`-SOCKnapsack`	Specifies the problem class as SOC Knapsack
`-Sequencing`	Specifies the problem class as Sequencing
`-FlowCuts`	Use combinatorial cuts (BDD problems only)
`-JointFlowCuts`	Use dual flow cuts (BDD problems only)
`-TargetCuts`	Use target cuts from relaxed MDD (all problems)
`-Exact`	Build the exact DD (default)
`-Restricted`	Build a restricted DD
`-RelaxPriority`	Build a relaxed DD (merge nodes by priority)
`-RelaxGrouping`	Build a relaxed DD (merge nodes in groups by priority difference)
`-Width_`	Sets the maximum width for Restricted/Relaxed DD (e.g. `-Width_100`)
`-CutStrengthening`	Apply cut strengthening after generation
`-Continuous`	Solve the LP relaxation (default: binary/MIP)
`-Verbose`	Enables verbose mode for detailed output
`-Output_`	Specifies the output file path

Execution Example

PythonC++

python3 ./main_cuts.py example_file.txt -SetCover -FlowCuts -Verbose -Output_result.txt

./main_cuts example_file.txt -SetCover -FlowCuts -Verbose -Output_result.txt

Output Example

When the program runs, it displays the following information:

Running with the following parameters:
Input File: example_input.txt
Output File: result.txt
Problem Class: Set Cover
Cut Type: FlowCuts
DD Type: Exact
Maximum Width: 2147483646
Strength Cuts: No
Verbose: Yes
Continuous: No

Notes

The program automatically determines the current directory and appends it to the input and output file paths to ensure all necessary files are correctly located.
If the -Output_ flag is omitted, no output file will be generated.
You must select a cut type (-FlowCuts, -JointFlowCuts, or -TargetCuts); the valid options depend on the problem class (BDD problems support all three, while the Sequencing MDD only supports -TargetCuts).
The strengthening procedure is only applied when using the -CutStrengthening flag.