Questions tagged [decomposition]
The decomposition tag has no usage guidance.
12
questions
1
vote
0
answers
34
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 ...
- 139
2
votes
1
answer
59
views
How do you derive the Benders feasibility cuts?
starting off with a MIP that I want to solve using Benders.
so in Benders Decomposition, you add feasibility cuts in the following form:
$v^j (b - Ax) \geq 0$
with $j \in J$ being the set of extreme ...
- 139
3
votes
1
answer
153
views
About Mathematical Programs
I am dealing with the following problem as follows.
$$\min \sum_{i,j}( x_{i}+y_{j}+q_{ij}+w_{i})$$
$$\text{s.t.} x_{i}+y_{j}+q_{ij}+w_{i} \geq b_{ij}, \forall i,j$$
Is it possible to handle this ...
user5245
2
votes
0
answers
73
views
Benders with MINLP subproblem as the pricing problem of Dantzig Wolfe
I have a convex MINLP that after a Dantzig-Wolfe reformulation, passes most of the difficulty onto the pricing problem, which becomes a convex MINLP itself.
The pricing problem should be solvable with ...
- 516
2
votes
0
answers
56
views
Minimizing sum of similar functions with a dependence
Consider an objective function in the form of minimization of maximization that is the sum of $N$ similar functions $f\left(x\right)\ge 0$, $\ \forall x$. The summation of all variables is constant (e....
3
votes
1
answer
141
views
Benders Decomposition for Fixed Charge Transportation Problem
I am trying to write down the steps in Benders decomposition for the Fixed Charge Transportation Problem and was hoping someone could confirm/deny whether my understanding of it is correct. The ...
- 31
1
vote
0
answers
71
views
Multi-Stage Stochastic Decomposition
I have a multi-stage model with both binary and continuous first-stage investment variables and continuous operational next-stage variables:
$$
\sum_{s} \rho_{s} \left[ x_{s} + y_{s} + \sum_{t}(y^{op}...
- 103
5
votes
3
answers
152
views
What is the go-to practical method for optimizing separable quadratic programs?
I have a quadratic program that looks like this:
For fixed vector $b$, and matrices $A_1, ..., A_n$, Find column vectors $x_1, ..., x_n$ that minimize $\sum_{i=1}^n x_i ^T 1 1^T x_i$ subject to $\sum_{...
- 151
3
votes
1
answer
475
views
Benders decomposition feasibility/ optimality cuts
I am trying to understand Benders Decomposition method. I am reading this book Decomposition techniques in mathematical programming by A Conejo, E Castillo, R Minguez. The book provides an example of ...
- 333
2
votes
1
answer
276
views
Benders Decomposition cuts for MILP problem with further separable subproblems
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 331
7
votes
1
answer
130
views
Minimizing sum of functions with pairwise dependence
I have formulated a problem where I need to minimize the sum of $N$ functions, with only pairwise dependence between the functions (any single constraint involves only two functions having adjacent ...
- 239
7
votes
1
answer
166
views
How to solve this variant of RCPSP
We have $m$ projects in parallel that require shared resources the resources has time varying capacities (i.e $B_{rt}$ is the units of resource $r$ available in period $t$). For each project there is $...
- 943