# Questions tagged [cuts]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 317
96 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 ...
• 8,960
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$$ ...
• 317
1 vote
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 ...
• 317
1 vote
264 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
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 ...
• 900
93 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 ...
• 317
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 ...