Skip to main content

Questions tagged [cuts]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers

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 ...
Arctic_Skill's user avatar
0 votes
0 answers

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 ...
A.Omidi's user avatar
  • 8,960
0 votes
1 answer

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 $$ ...
Arctic_Skill's user avatar
1 vote
0 answers

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 ...
Arctic_Skill's user avatar
1 vote
0 answers

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 ...
CHE's user avatar
  • 113
0 votes
0 answers

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 ...
Brannon's user avatar
  • 900
2 votes
2 answers

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 ...
Arctic_Skill's user avatar
3 votes
2 answers

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 ...
Clement's user avatar
  • 2,252