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 Rune 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 add cuts if need be in an iterative fashion. The Example folder includes a GurobiClass version for each of our example problems (i.e., KnapsackGurobiClass, IndependtSetGurobiClass, and SetCoveringGurobiClass), and the Examples/GuiHandler file has code for all these problem examples.

1. Define parameters and create knapsack instance

We first provide the program with all the necessary parameters to create a knapsack problem instance (e.g., items weights and knapsack capacity). Our implementation includes a KnapsackStructure class that reads all such parameters from an input file. Then, we create a KnapsackProblem object with the provided parameters. Recall that KnapsackProblem also includes relevant information to create a DD, such as the initial_state and the domain of the variables. Additional details on how to create a knapsack instance can be found in the Problem implementation page.

PythonC++

 knapsack_parameters: KnapsackStructure = KnapsackStructure(gui_cuts_structure.input_file_path)

 problem_instance: KnapsackProblem = KnapsackProblem(knapsack_parameters.initial_state,
                                                    knapsack_parameters.variables,
                                                    knapsack_parameters.weights,
                                                    knapsack_parameters.right_side_of_restrictions)

KnapsackInstance* knapsack_parameters = new KnapsackInstance(gui_cuts_structure.input_file_path);

KnapsackProblem problem_instance(knapsack_parameters->initial_state, 
                                knapsack_parameters->variables, 
                                knapsack_parameters->weights, 
                                knapsack_parameters->right_side_of_restrictions);

2. Create an instance of KnapsackGurobi

Create an instance of the KnapsackGurobiClass (details of this class can be found in the file Examples/KnapsackInstance/KnapsackGurobiClass). When initializing the instance, it is necessary to provide variable_length, weights, objective_weights, capacity, and indicate that the variables are continuous.

Notes:

• KnapsackGurobiClass and any other problem class that inherits from AbstractProblemGurobiClass always creates variables with binary domain. As a consequence, the provided example does not support knapsack instances with general integer variables.
• We require continuous variables in the KnapsackGurobiClass since we are solving the problem using a cutting plane approach. However, a user can solve the same problem using the MILP optimization engine provided by Gurobi specifying that the variables are integer.

PythonC++

gurobi_instance: KnapsackGurobi = KnapsackGurobi(len(knapsack_parameters.variables),
                                    knapsack_parameters.weights, 
                                    knapsack_parameters.objective_weights, 
                                    knapsack_parameters.right_side_of_restrictions, 
                                    gui_cuts_structure.continuous_flag)

gurobi_instance.create_model()

KnapsackGurobiClass gurobi_instance(knapsack_parameters->variables.size(), 
                                    knapsack_parameters->weights, 
                                    knapsack_parameters->objective_weights, 
                                    knapsack_parameters->right_side_of_restrictions,
                                    gui_cuts_structure.continuous_flag);

gurobi_instance.create_model();

3. Create DD

We then construct an exact DD using the various features explained in the previous examples. At least one DD (either exact or relaxed) must be created, and the reduced version of such a DD can also be used.

PythonC++

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

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

4. Cut generators and lifting

Next, we create a CutGenerator from one of the available options (i.e., FlowCuts or JointFlowCuts) by providing the DD created in step 3. You can also create an object of the LiftCut class to strengthen the cuts provided by the cut generator.

PythonC++

cuts_instance: 'AbstractCut' = None

if gui_cuts_structure.flow_cut_flag:
    cuts_instance = FlowCuts(dd_instance)
elif gui_cuts_structure.joint_cut_flag:
    cuts_instance = JointFlowCuts(dd_instance)


lift_cut_instance: LiftCut = None

if gui_cuts_structure.lift_cuts_flag:
    lift_cut_instance: LiftCut = LiftCut(dd_instance, gui_cuts_structure.verbose)

AbstractCutGenerator<T> *cuts_instance = nullptr;

if (gui_cuts_structure.flow_cut_flag) {
    cuts_instance = new FlowCuts<T>(&dd_instance);
} else if (gui_cuts_structure.joint_cut_flag) {
    cuts_instance = new JointFlowCuts<T>(&dd_instance);
}


LiftCut<T> *lift_cut_instance = nullptr;

if (gui_cuts_structure.lift_cuts_flag) {
    lift_cut_instance = new LiftCut<T>(&dd_instance, gui_cuts_structure.verbose);
}

5. Get cuts and add them to the Gurobi model

The cutting plane procedure adds cuts and re-optimize the model using Gurobi while the solution is not integer. To do this, start by providing the values of the variables from the solution generated by Gurobi to the generate_cut() method of your CutGenerator (i.e., FlowCuts or JointFlowCuts). If it returns a positive boolean, the CutGenerator found a cut, which can be obtained with the get_cut() function. The cut (i.e., coefficients and right-hand-side constant) can be provided to the lift_cut() method of the LiftCut class to obtain a stronger inequality. If the cut is successfully lifted, use the get_lift_cut() function to obtain the resulting inequality. Lastly, the cut should be added to the Gurobi model. To do this, use the add_additional_cuts() method and then optimize the updated model with the optimize_model() function.

PythonC++

gurobi_instance.optimize_model()
number_of_new_cuts: int = 0

while not are_all_variables_integer(gurobi_instance.model):
    cuts: list = []

    if cuts_instance.generate_cut(gurobi_instance.model.getAttr('x'), gui_cuts_structure.verbose):
        number_of_new_cuts += 1
        coefficients, constant = cuts_instance.get_cut()

        if gui_cuts_structure.lift_cuts_flag and lift_cut_instance and lift_cut_instance.lift_cut(coefficients, constant):
            cuts.append(lift_cut_instance.get_lift_cut())
        else:
            cuts.append(cuts_instance.get_cut())
    else:
        print("No cuts that provide an integer solution could be found.")
        break

    gurobi_instance.add_additional_cuts(cuts)
    gurobi_instance.optimize_model()

gurobi_instance.optimize_model();
int number_of_new_cuts = 0;

while (!are_all_variables_integer(gurobi_instance.model)) {
    vector<pair<vector<double>, double>> cuts;
    vector<double> variable_values;

    for (int i = 0; i < gurobi_instance.model->get(GRB_IntAttr_NumVars); ++i) {
        variable_values.push_back(gurobi_instance.model->getVar(i).get(GRB_DoubleAttr_X));
    }

    if (cuts_instance->generate_cut(variable_values, gui_cuts_structure.verbose)) {
        vector<double> coefficients;
        double constant;
        tie(coefficients, constant) = cuts_instance->get_cut();
        number_of_new_cuts ++;

        if (gui_cuts_structure.lift_cuts_flag and lift_cut_instance != nullptr and lift_cut_instance->lift_cut(coefficients, constant)) {
            cuts.push_back(lift_cut_instance->get_lift_cut());
        } else {
            cuts.push_back(cuts_instance->get_cut());
        }
    } else {
        cout << "No cuts that provide an integer solution could be found." << endl;
        break;
    }

    gurobi_instance.add_additional_cuts(cuts);
    gurobi_instance.optimize_model();
}