Runing DD-suite

DD-suite includes three main files (i.e., programs) to run all the basic features provided by the tool over the three discrete optimization problems that we provide as examples (i.e., Knapsack, Independent Set, and Set Covering). 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 -SetCovering, -Knapsack, or -IndependentSet). 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 three problem classes in the DataInstances folder. We provide a folder for each problem class (i.e., Knapsack, IndependentSet, and SetCovering), and there are two folders inside each one: Custom and Standard. The files in Standard are instances found in the literature with their original formatting. On the other hand, the files in Custom correspond to a more straightforward format that all three programs can read. Therefore, the user needs to use the files in the Custom folder to try any of the three default programs provided in DD-suite or create input files with the same format as the ones in Custom. As an example, a valid input data for main with the -SetCovering flag is:

DataInstances/SetCovering/Custom/set_covering_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
`-SetCovering`	Specifies the problem class as Set Covering
`-Knapsack`	Specifies the problem class as Knapsack
`-IndependentSet`	Specifies the problem class as Independent Set
`-Exact`	Specifies the DD type as Exact
`-Restricted`	Specifies the DD type as Restricted
`-Relaxed`	Specifies the DD type as Relaxed
`-width_`	Sets the maximum width for Restricted/Relaxed DD
`-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
`-output_`	Specifies the output file path

Execution Example

PythonC++

python3 ./main.py example_input.txt -SetCovering -Relaxed -width_100 -Reduce -Verbose -output_result.txt

./main example_input.txt -SetCovering -Relaxed -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 Covering
DD Type: Relaxed
Maximum Width: 100
Reduce: Yes
Verbose: Yes
Export: No
Min/Max?: min

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 a large integer value).
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 three specified problem classes: Set Covering, Knapsack, and Independent Set. 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
`-SetCovering`	Specifies the problem class as Set Covering
`-Knapsack`	Specifies the problem class as Knapsack Instance
`-IndependentSet`	Specifies the problem class as Independent Set
`-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 -SetCovering -Verbose -output_solution.txt

./main_gurobi example_input.txt -SetCovering -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 Covering
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 lift) DD-based cuts (i.e., Flow Cuts or JointFlow 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
`-SetCovering`	Specifies the problem class as Set Covering
`-Knapsack`	Specifies the problem class as Knapsack Instance
`-IndependentSet`	Specifies the problem class as Independent Set
`-Verbose`	Enables verbose mode for detailed output
`-FlowCuts`	Select combinatorial cuts to the model
`-JointFlowCuts`	Select dual cuts to the model
`-Lift`	Select lifting procedure
`-output_`	Specifies the output file path

Execution Example

PythonC++

python3 ./main_cuts.py example_file.txt -SetCovering -FlowCuts -Verbose -output_result.txt

./main_cuts example_file.txt -SetCovering -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 Covering
Flow Cuts: True
JointFlow Cuts: False
Lift Cuts:  No
Verbose: 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.
If the -output_flag is omitted, no output file will be generated.
Default behavior uses Flow Cuts unless de -JointFlowCuts flag is provided.
The lifting procedure is only consider when using the -Lift flag.