Skip to content

Cuts

Detailed Explanation of Optimization Problems and Their Implementations

For a comprehensive understanding of these classes, it is recommended to thoroughly review the examples available in the "/Examples/" folder within the code and execute Knapsack/KnapsackGurobiMain. These examples are generic and open for testing different values. Below, we will explain the examples in detail.

Example:

Consider a set of items:

  • Item 1: Weight = 7, Value = 1
  • Item 2: Weight = 3, Value = 1
  • Item 3: Weight = 2 Value = 1
  • Item 3: Weight = 1 Value = 1

And a knapsack with a capacity of 8.

The goal is to select items such that their total weight is ≤ 8 and their total value is maximized. However, if solved with Gurobi using continuous variables, the result will be 0.28 of item 1 and 1 of items 2, 3, and 4. But it is necessary for the solution to be integer. To achieve this, cuts can be added as constraints to the model until an integer solution is obtained. The process to follow is to provide the value of the variables to the Cut class. If an inequality is obtained, pass it to the LiftCut class and then add it to the model.

Implementation

In the KnapsackGurobiMain file, you will find a generalized version of this linear problem, allowing for flexible input of variable weights and constraints. Here's a step-by-step explanation of how to work with the knapsack problem:

1. Input Weights and Constraints:
  • Provide the weights of the variables in the different constraints using the matrix_of_weight parameter.
  • Specify the right side of the constraints in the right_side_of_restrictions parameter, the weight capacity.
2. Define Initial State and Variables:
  • Set the initial state in the initial_state parameter, for example, 0 if this refers to the selected weight up to that minute.
  • Provide the variables along with their domain in the variables parameter, if it's binary you should use {0,1}.
3. Create an Instance of KnapsackGurobi:
  • With the weights and constraints provided, create an instance of KnapsackGurobi. The details of this class can be found in the file Examples/KnapsackGurobiClass. When initializing the instance, it is necessary to provide variable_length, matrix_of_weights, objective_weights, right_side_of_restrictions, and indicate that the variables are continuous with continuous=True.
4. Generate Decision Diagram:
  • After defining all the parameters, generate a decision diagram using the various features explained earlier. In the knapsack example, it is necessary to create at least one exact diagram, although its reduced version can also be used.
5. Instances of Cuts:
  • Create cut_instances of a cut clas (ex. CombinatorialCutor DualCut) and lift cuts (LiftCut) by providing the decision diagram created in step 4 when instantiating them.
6. Get Cuts:
  • While the solution is not integer, add additional cuts and optimize the model using Gurobi. To do this, start by providing the values of the variables from the solution generated by Gurobi to the generate_cut() method of the cut_instances. If it returns a positive boolean, it means a cut was found, which can be obtained with the get_cut function. These values 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 inequality.
7. Add Cut To The Gurobi Model:
  • Finally, the cut should be added to the Gurobi model. To do this, use the add_additional_cuts() method and then recalculate the optimal solution with the optimize_model() function.