Questions tagged [decomposition]
The decomposition tag has no usage guidance.
16
questions
1
vote
0
answers
44
views
How to decompose a specific constraint in the sub-problem?
Suppose there is a specific constraint as follows to impose the precedence relation between the tasks:
$$ \sum_{m \in M} m.x_{j,m} \leq \sum_{m \in M} m.x_{k,m} \quad \forall (j,k) \in T $$
I want to ...
- 9,248
0
votes
0
answers
30
views
Regarding Benders Decomposition for Master Problem with Binary Variables and Sub-problem with Integers (Not Continuous Variables) [duplicate]
I have a question on Benders Decomposition (BD). I have a MILP model which can be decomposed into a master problem (MP) comprising only binary variables and a subproblem (SP) though containing only ...
- 793
1
vote
0
answers
49
views
How to decompose the problem with overlapping blocks?
If the original problem contains the diagonal block structure property or other specific properties then we can apply column generation or other decomposition algorithms to solve it.
However, if the ...
- 411
3
votes
1
answer
100
views
How to modify Benders decomposition to handle overlapping or shared variables among the subproblems
I have a problem that can be separated into a master problem and two subproblems, SP-A and SP-B. SP-B share some variables with SP-A, and the shared/overlapping variables from SP-A cannot be fixed for ...
- 33
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
2
votes
1
answer
239
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 ...
- 327
3
votes
1
answer
159
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
85
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 ...
- 650
2
votes
0
answers
66
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
185
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}...
- 113
5
votes
3
answers
159
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
599
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
3
votes
1
answer
306
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 ...
- 341
7
votes
1
answer
138
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
182
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 $...
- 973