Questions tagged [benders-decomposition]
For questions related to Benders decomposition, a type of optimization algorithm in which certain variables are optimized in a "master problem," the values of those variables are fixed, the remaining variables are optimized in a "subproblem," cuts are generated to be added to the master problem, and the method repeats.
94 questions
1
vote
1
answer
60
views
Why does my LazyConstraintCallback sometimes skip incumbent solutions in CPLEX?
I am implementing a Logic-Based Benders Decomposition in Python with CPLEX. My setup is the following:
The master problem (MP) decides a sequencing/assignment structure.
The subproblem (SP) is solved ...
1
vote
1
answer
167
views
Benders Cuts Discrete Variables
I am applying SDDP to a multistage stochastic program where both the state variables and local variables are a combination of integer and continuous variables (Subproblems are MILP). To extract the ...
- 125
0
votes
0
answers
129
views
Farkas Dual to generate Feasibility Cuts
I want to solve a network design problem with Benders decomposition. Its subproblem complicated ones with different ranges for each constraint making the dual impossible to find, so I've decided to go ...
- 61
1
vote
1
answer
170
views
Benders subproblem optimality cut value differs from subproblem obj function
I'm working on implementing Benders decomposition for a MILP problem. The approach is quite straightforward: all integer variables are assigned to the Master Problem (MP), while all continuous ...
- 147
2
votes
0
answers
164
views
Combinatorial Benders Cut - fastest way to find Irreducible Infeasible Subsystems (IIS)
I reformulated a VRP problem via combinatorial Benders Decomposition, moving all Big-M constraints to the Linear program (LP) sub problem.
I implemented the Benders approach in Gurobi, if I find an ...
- 121
1
vote
1
answer
94
views
Significant and Strange Time Discrepancy Between Direct Solution and Generic Callback-Based Approach for Solving an Instance
I am attempting to solve a MILP using logic-based Benders decomposition (LBBD) via generic callbacks, but I have encountered some unexpected behavior.
When solving the MILP directly, the problem is ...
- 13
2
votes
0
answers
82
views
Benders Cut Concerning Objective
I am trying to generate a linear lower bound approximation for a subproblem of Benders Decomposition:
$$
\begin{align}
V(z_1,z_2) = \min_{y} \quad & (q-z_1)^\top y \\
\text{s.t.} \quad & ...
- 21
1
vote
1
answer
134
views
Combinatorial Benders Papers which solve MIPs with binary master problems and continuous subproblems having subproblem objective functions
I am currently solving a problem of the aforementioned type containing Big-M constraints.
The seminal paper by Codato, G., & Fischetti, M., dated 2006, Combinatorial Benders' cuts for mixed-...
- 803
1
vote
1
answer
150
views
Infeasibility of subproblem in Combinatorial Benders Decomposition
I am working on a problem that is suitable to be applied with the Combinatorial Benders decomposition.
I read the Fischetti and Codato paper about the topic in order to implement it.
Probably I did ...
- 23
4
votes
2
answers
202
views
Big-M Constraints in Benders Decomposition
I am studying a typical MILP problem with the form:
$$
\begin{align}
\min \;& c^Tx+d^Ty \\
\text{s.t.} \; & Fx\leqslant g\\
\; & Dy\leqslant e\\
\; & y\leqslant Mx\\
\; & x\in\{...
- 41
0
votes
0
answers
96
views
How to get an extreme ray in CPLEX
I am trying to get an extreme ray in a Benders decomposition when the primal subproblem is infeasible (so, the dual is unbounded). CPLEX below propose some function but no one works.
If you are using ...
- 1
1
vote
0
answers
83
views
Using the Alternative Cut Generation Problem in Benders, why do I get different results?
I am using Benders' Decomposition to solve a stochastic MIP.
To improve cut selection, I implemented the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010).
I will summarize the ...
- 389
0
votes
1
answer
75
views
How can I calculate the UB if I'm using Fischetti's Alternative Cut Generation for Benders'?
Assuming I have a stochastic MIP that I want to minimize using Benders' Decomposition.
With the objective of the MP being:
$$
Minimize \; cx + \frac{1}{\lvert S \rvert} \sum_{s \in S} \theta_s
$$
...
- 389
4
votes
1
answer
226
views
Benders Decomposition Implementation - Should I keep the old feasibility cut in master problem?
I am currently working on combinatorial subproblems. First, I need to solve the master problem, find all possible subproblems, solve each combination individually, and ensure all the subproblems are ...
- 41
1
vote
0
answers
153
views
CPLEX gets stuck in "Performing restart"
During solving my problem using generic lazy cuts (in Benders decomposition fashion), the solver gets stuck logging out "Performing restart 2" for several hours (while the time limit is 30 ...