# Questions tagged [decomposition]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
1 vote
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}...