Skip to main content

Questions tagged [decomposition]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
47 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 ...
ytsao's user avatar
  • 386
3 votes
1 answer
97 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 ...
user4444's user avatar
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 ...
Arctic_Skill's user avatar
2 votes
1 answer
117 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 ...
Arctic_Skill's user avatar
3 votes
1 answer
157 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 ...
user avatar
2 votes
0 answers
76 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 ...
J. Dionisio's user avatar
2 votes
0 answers
61 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....
Reza Farahani's user avatar
3 votes
1 answer
160 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 ...
BftA's user avatar
  • 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}...
Ahmed's user avatar
  • 113
5 votes
3 answers
156 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_{...
AspiringMat's user avatar
3 votes
1 answer
569 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 ...
Jonn's user avatar
  • 333
2 votes
1 answer
286 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 ...
Amogh Bhosekar's user avatar
7 votes
1 answer
137 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 ...
V-Red's user avatar
  • 239
7 votes
1 answer
173 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 $...
Joffrey L.'s user avatar