Compute Lagranigan Bound
AnsweredHello, I asked this question today on Operations Research Stack Exchange about how to determine whether a found solution of a Column Generation approach is optimal for a MIP. The answer was that I have to calculate the Lagranigan Bound. How does this work in Gurobi?
-
Hi Dejan,
Solving a Lagrangian dual problem with Gurobi involves formulating the Lagrangian relaxation of your original problem and then using an iterative algorithm to solve it. This approach is particularly useful when dealing with problems that are difficult to solve directly, but can be simplified by relaxing some constraints and incorporating them into the objective function with penalty terms.
The basic steps to solve a Lagrangian dual with Gurobi are as follows:
1. **Formulate the Lagrangian Relaxation**: Identify the constraints to relax from your original problem. These are typically constraints that make the problem hard to solve directly. For each constraint you relax, introduce a Lagrange multiplier and add a term to the objective function that represents the penalty for violating the relaxed constraint.
2. **Solve the Lagrangian Subproblem**: For fixed values of the Lagrange multipliers, solve the modified problem (now a Lagrangian subproblem). This subproblem should be easier to solve than the original problem. You can use Gurobi's optimization functions to solve this subproblem.
3. **Update Lagrange Multipliers**: Use a subgradient optimization method or any other suitable method to update the values of the Lagrange multipliers based on the solution of the subproblem and the degree of violation of the relaxed constraints.
4. **Iterate**: Repeat steps 2 and 3 until convergence criteria are met. This could be based on the change in the objective function value, the change in the values of the Lagrange multipliers, or both.
To implement this in Gurobi, you'll need to:
- Use the `Model()` function to create new models for the Lagrangian subproblems.
- Adjust the objective function by adding the penalty terms associated with the relaxed constraints.
- Use the `optimize()` method to solve each subproblem.
- Manually implement the logic for updating the Lagrange multipliers and checking for convergence.Unfortunately, the Gurobi documentation included does not provide a direct example or instructions specifically for solving a Lagrangian dual problem. Solving such problems typically requires a more hands-on approach with custom algorithmic steps as outlined above.
The following YouTube video may be useful:
Duality: Lagrangian and dual problem
Michel Bierlaire- Gurobot
0
Please sign in to leave a comment.
Comments
1 comment