Cutting planes

We now explain how to use the provided cutting plane implementation of DD-suite. Recall that this implementation is quite simple and is provided just to illustrate the versatility and compatibility of DD-suite with other optimization tools, such as Gurobi.

For a comprehensive understanding of our implementation, we recommend thoroughly reviewing the methods gurobi_dd_cutting_planes() and run_gurobi_dd() available in the Examples/GuiHandler folder within the code and executing main_cuts (see Run Code for further details).

Implementation

We provide a step-by-step explanation for solving a problem instance using the cutting plane procedure, focusing on the knapsack problem for illustrative purposes. Our cutting plane procedure uses the KnapsackGurobiClass to create a continuous version of the problem, solve it, and inject DD-based cuts via a Gurobi callback. The Examples/ folder includes a GurobiClass version for each of our example problems (KnapsackGurobiClass, IndependentSetGurobiClass, SetCoverGurobiClass, SOCKnapsackGurobiClass, SchedulerGurobiClass), and the Examples/GuiHandler file has code for all these problem examples.

1. Load the instance and create the problem

We first load all the necessary parameters from a file using the instance reader class (KnapsackStructure in Python, KnapsackInstance in C++). Then, we create a KnapsackProblem object, which holds the DD-specific information such as initial_state and variable domains. Additional details can be found in the Problem implementation page.

PythonC++

from Examples.KnapsackInstance.KnapsackInstance import KnapsackStructure
from Examples.KnapsackInstance.KnapsackProblem import KnapsackProblem

knapsack_parameters = KnapsackStructure(file_path)
problem_instance = KnapsackProblem(knapsack_parameters)

#include "Examples/KnapsackInstance/KnapsackInstance.h"
#include "Examples/KnapsackInstance/KnapsackProblem.h"

KnapsackInstance knapsack_parameters(file_path);
KnapsackProblem  problem_instance(knapsack_parameters);

2. Create the Gurobi instance

Create an instance of KnapsackGurobiClass by passing the instance parameters and a flag indicating whether variables should be continuous. Continuous variables are required for the cutting plane approach; set continuous=False to use Gurobi's MILP engine directly instead.

Notes:

• KnapsackGurobiClass and all classes that inherit from AbstractProblemGurobiClass create binary variables by default.
• Pass continuous=True when using DD cuts, since the cutting plane procedure works on the LP relaxation.

PythonC++

from Examples.KnapsackInstance.KnapsackGurobiClass import KnapsackGurobi

gurobi_instance = KnapsackGurobi(knapsack_parameters, continuous=True)
gurobi_instance.create_model()

#include "Examples/KnapsackInstance/KnapsackGurobiClass.h"

KnapsackGurobiClass gurobi_instance(knapsack_parameters, /*continuous=*/true);
gurobi_instance.create_model();

3. Create the DD

Construct a DD from the problem instance. Both exact and relaxed DDs are valid. Optionally apply reduction.

PythonC++

from SourceCode.DD import DD

dd_instance = DD(problem_instance)
dd_instance.create_decision_diagram(verbose=False)
dd_instance.reduce_decision_diagram(verbose=False)

#include "SourceCode/DD.h"

DD<int> dd_instance(problem_instance);
dd_instance.create_decision_diagram(false);
dd_instance.reduce_decision_diagram(false);

4. Choose a cut generator

Three cut generators are available, selected via the CutType enum:

CutType value	Class	DD type required	Description
CutType.FLOW	FlowCuts	Binary (BDD)	Combinatorial min-cut based cuts
CutType.JOINT_FLOW	JointFlowCuts	Binary (BDD)	Dual flow cuts, typically tighter than FlowCuts
CutType.TARGET	TargetCut	Any (MDD/BDD)	LP-based target cuts (Tjandraatmadja & van Hoeve, 2019); works for multi-valued domains

Cut strengthening (via CutStrengthening) can be applied on top of FlowCuts or JointFlowCuts by passing cut_strengthening=True.

5. Optimize with DD cuts

Call optimize_with_cuts with the list of DDs, the chosen cut type, and whether to apply strengthening. The cutting plane loop is handled automatically via a Gurobi MIP node callback — no manual iteration is needed.

PythonC++

from Examples.GuiStructure import CutType

gurobi_instance.optimize_with_cuts(
    [dd_instance],
    cut_type=CutType.JOINT_FLOW,
    cut_strengthening=True
)

#include "Examples/GuiStructure.h"

gurobi_instance.optimize_with_cuts(
    vector<DD<int>*>{&dd_instance},
    CutType::JointFlow,
    /*cut_strengthening=*/true
);

The method automatically:

1. Instantiates the selected cut generator (and optional strengthener) for each provided DD.
2. Registers a Gurobi MIP node callback that, at the root node, extracts the current LP relaxation, calls generate_cut(), and injects the resulting inequality into the model via cbCut().
3. Re-optimizes until no further cuts are found or the solution is integer.

To use target cuts instead, simply change the cut type:

PythonC++

gurobi_instance.optimize_with_cuts(
    [dd_instance],
    cut_type=CutType.TARGET
)

gurobi_instance.optimize_with_cuts(
    vector<DD<int>*>{&dd_instance},
    CutType::Target
);