# Questions tagged [decomposition]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
182 views

• 151
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
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
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
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 ...
159 views

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 ...
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
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
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....
1 vote
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
1 vote
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
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 ...
• 327
1 vote
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
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