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 fileExamples/KnapsackGurobiClass
. When initializing the instance, it is necessary to providevariable_length
,matrix_of_weights
,objective_weights
,right_side_of_restrictions
, and indicate that the variables are continuous withcontinuous=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.
CombinatorialCut
orDualCu
t) 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 theget_cut
function. These values can be provided to thelift_cut()
method of theLiftCut
class to obtain a stronger inequality. If the cut is successfully lifted, use theget_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 theoptimize_model()
function.