Questions tagged [cuts]
The cuts tag has no usage guidance.
8
questions
1
vote
0
answers
37
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 ...
- 327
0
votes
0
answers
97
views
Tightening a specific constraint
I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
- 9,068
0
votes
1
answer
42
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
$$
...
- 327
1
vote
0
answers
43
views
Is there a way to calcuate the maximum number of cuts in a Benders decomposition?
Since the benders algorithm is finite, there a maximum number of cuts that could theoretically be added. The worst case is that I add cuts for all extreme points and all extreme rays that are part of ...
- 327
1
vote
0
answers
267
views
Deriving a valid inequality
Given a set of facilities $I$ and days $J$, each facility $i \in I$ has a capacity of $C_i$, and a set of days $J$ where in each day $j \in J$ there's a total demand of $q_j$ that can be satisfied by ...
- 113
0
votes
0
answers
90
views
why the -1 in basis column for simplex tableau?
When I look at the tableau generated by Gurobi for a simple 3D problem with five constraints, I get this:
I expected to not have a -1 in basis columns 4, 5, 6 (referring to slack variables 1, 2, 3 if ...
- 920
2
votes
2
answers
96
views
In Benders Decomposition, do you add an optimality cut together with a feasibility cut?
in the process of implementing my first BD algorithm, I am unsure how to proceed in the case that the subproblem is unbounded.
Obviously, it means you get an extreme ray that you can add to the RMP as ...
- 327
3
votes
2
answers
115
views
Knapsack Constraint
Is the following expression a knapsack constraint?
$ \sum_i a(i) y(i) \ge W$, where $y(i)$ binaries, $a(i),W$ reals.
What confuses me is the $\ge$ sign.
Alternatively, do solvers generate cuts out of ...
- 2,252