Questions tagged [dantzig-wolfe-decomposition]

For questions on a method that transforms a subset of the linear inequalities of a linear program into an equivalent representation by its extreme points and rays; this generally introduces a large number of new variables.

Filter by
Sorted by
Tagged with
1
vote
1answer
41 views

How to deal with the sub-problem with zero reduced cost in D-W decomposition

The specific linear programme has an optimal solution as $x_1 = 0.66$, $x_2 = 1.33$, $x_3 = 12.2$, $x_4 = 0.0$ and the objective value is $33.3$. While the problem is solved by D-W decomposition ...
1
vote
1answer
235 views

Can I apply decomposition methods for this scheduling problem

I have a centralized optimization problem for a residential area in the context of a smart grid and load flexibility. So let's say I have 10 buildings and each of them has an electric heating device. ...
2
votes
0answers
52 views

Dantzig decomposition and Column Generation for equality constraints

I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught. \begin{array}{l} \text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\ \text { subject to: } x_{1}+...
8
votes
3answers
667 views

How can I initialize the Restricted Master Problem in Dantzig-Wolfe decomposition?

I am attempting to solve a linear program via Dantzig-Wolfe decomposition. It is the first time I implement this method. Before the pricing iterations start, I need to provide an initial set of ...
7
votes
1answer
148 views

Is Dantzig-Wolfe decomposition finite if variables are unbounded?

Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this: $$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$ They argue that $P_j$ ...
10
votes
0answers
122 views

Column generation for TSP

For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach. In the academic literature, an approach is proposed (for example here), where columns ...
14
votes
2answers
353 views

What are the modern optimization methods for large systems?

I came across the preface of Optimization Theory for Large Systems (you can read it in Amazon). The author claims in the table (page v) that some of the methods such as Dantzig Wolfe decomposition, ...
17
votes
2answers
216 views

Automating the column generation decomposition process

When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then: Decide what a column should represent Write the Master Problem Write ...
16
votes
4answers
400 views

Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition

It’s often said that “Benders’ decomposition is Dantzig-Wolfe applied to the dual”. How can this statement be made precise? I know that in Dantzig-Wolfe, cuts are added in one-to-one correspondence ...