187:
has completed and then incorporate all columns that improve the objective or it may choose a smaller subset of those columns. Another option is that the master may take only the first available column and then stop and restart all of the subproblems with new objectives based upon the incorporation of the newest column.
186:
The algorithm can be implemented such that the subproblems are solved in parallel, since their solutions are completely independent. When this is the case, there are options for the master program as to how the columns should be integrated into the master. The master may wait until each subproblem
53:, at each step, most columns (variables) are not in the basis. In such a scheme, a master problem containing at least the currently active columns (the basis) uses a subproblem or subproblems to generate columns for entry into the basis such that their inclusion improves the objective function.
114:
Each column in the new master program represents a solution to one of the subproblems. The master program enforces that the coupling constraints are satisfied given the set of subproblem solutions that are currently available. The master program then requests additional solutions from the
61:
In order to use
Dantzig–Wolfe decomposition, the constraint matrix of the linear program must have a specific form. A set of constraints must be identified as "connecting", "coupling", or "complicating" constraints wherein many of the variables contained in the constraints have non-zero
190:
Another design choice for implementation involves columns that exit the basis at each iteration of the algorithm. Those columns may be retained, immediately discarded, or discarded via some policy after future iterations (for example, remove all non-basic columns every 10 iterations).
62:
coefficients. The remaining constraints need to be grouped into independent submatrices such that if a variable has a non-zero coefficient within one submatrix, it will not have a non-zero coefficient in another submatrix. This description is visualized below:
127:
Starting with a feasible solution to the reduced master program, formulate new objective functions for each subproblem such that the subproblems will offer solutions that improve the current objective of the master
134:
The master program incorporates one or all of the new columns generated by the solutions to the subproblems based on those columns' respective ability to improve the original problem's objective.
471:
35:
67:
331:. International Series in Operations Research & Management Science. Vol. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325.
194:
A (2001) computational evaluation of
Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth
123:
While there are several variations regarding implementation, the
Dantzig–Wolfe decomposition algorithm can be briefly described as follows:
131:
Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program.
336:
168:
496:
31:
491:
180:
208:
203:
42:
83:
represents the independent submatrices. Note that it is possible to run the algorithm when there is only one
34:
and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this
364:(reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc. pp. xiii+523.
172:
95:
After identifying the required form, the original problem is reformulated into a master program and
171:
mathematical modeling software. There are general, parallel, and fast implementations available as
151:
The master program cannot be further improved by any new columns from the subproblems, thus return.
465:
104:
23:
452:
332:
100:
50:
46:
99:
subprograms. This reformulation relies on the fact that every point of a non-empty, bounded
237:
369:
346:
313:
365:
342:
309:
160:
There are examples of the implementation of
Dantzig–Wolfe decomposition available in the
66:
228:
George B. Dantzig; Philip Wolfe (1960). "Decomposition
Principle for Linear Programs".
115:
subproblem such that the overall objective to the original linear program is improved.
108:
27:
485:
161:
301:
49:
of large-scale linear programs. For most linear programs solved via the revised
405:
430:
383:
241:
16:
Algorithm for solving linear programming problems with special structure
26:
problems with special structure. It was originally developed by
176:
164:
460:(PhD thesis). University of Buckingham, United Kingdom.
148:
If objective is improved, goto step 1. Else, continue.
304:(1996). "Simplex algorithms". In J. E. Beasley (ed.).
454:
A computational study of
Dantzig-Wolfe decomposition
76:
matrix represents the coupling constraints and each
384:"AMPL code repository with Dantzig–Wolfe example"
255:Dimitris Bertsimas; John N. Tsitsiklis (1997).
329:Computational techniques of the simplex method
8:
272:Linear Programming 2: Theory and Extensions
270:George B. Dantzig; Mukund N. Thapa (1997).
141:iterations of the simplex algorithm, where
470:: CS1 maint: location missing publisher (
431:"Open source Dantzig-Wolfe implementation"
306:Advances in linear and integer programming
220:
463:
145:is the number of columns incorporated.
41:Dantzig–Wolfe decomposition relies on
407:Dantzig-Wolfe Decomposition with GAMS
362:Optimization theory for large systems
7:
14:
308:. Oxford Science. pp. 1–46.
65:
451:Tebboth, James Richard (2001).
404:Kalvelagen, Erwin (May 2003),
1:
360:Lasdon, Leon S. (2002).
175:, including some provided by
22:is an algorithm for solving
20:Dantzig–Wolfe decomposition
513:
181:GNU Linear Programming Kit
204:Delayed column generation
43:delayed column generation
137:Master program performs
103:can be represented as a
36:decomposition algorithm
327:Maros, István (2003).
285:Vašek Chvátal (1983).
209:Benders' decomposition
497:Decomposition methods
91:Problem reformulation
259:. Athena Scientific.
242:10.1287/opre.8.1.101
173:open-source software
257:Linear Optimization
230:Operations Research
492:Linear programming
287:Linear Programming
105:convex combination
45:for improving the
24:linear programming
101:convex polyhedron
51:simplex algorithm
504:
476:
475:
469:
461:
459:
448:
442:
441:
439:
437:
427:
421:
419:
418:
417:
412:
401:
395:
394:
392:
390:
380:
374:
373:
357:
351:
350:
324:
318:
317:
297:
291:
290:
282:
276:
275:
267:
261:
260:
252:
246:
245:
225:
69:
512:
511:
507:
506:
505:
503:
502:
501:
482:
481:
480:
479:
462:
457:
450:
449:
445:
435:
433:
429:
428:
424:
415:
413:
410:
403:
402:
398:
388:
386:
382:
381:
377:
359:
358:
354:
339:
326:
325:
321:
300:Maros, István;
299:
298:
294:
284:
283:
279:
269:
268:
264:
254:
253:
249:
227:
226:
222:
217:
200:
158:
121:
93:
81:
59:
17:
12:
11:
5:
510:
508:
500:
499:
494:
484:
483:
478:
477:
443:
422:
396:
375:
352:
337:
319:
292:
277:
262:
247:
219:
218:
216:
213:
212:
211:
206:
199:
196:
157:
156:Implementation
154:
153:
152:
149:
146:
135:
132:
129:
120:
117:
109:extreme points
92:
89:
79:
58:
55:
28:George Dantzig
15:
13:
10:
9:
6:
4:
3:
2:
509:
498:
495:
493:
490:
489:
487:
473:
467:
456:
455:
447:
444:
432:
426:
423:
409:
408:
400:
397:
385:
379:
376:
371:
367:
363:
356:
353:
348:
344:
340:
338:1-4020-7332-1
334:
330:
323:
320:
315:
311:
307:
303:
302:Mitra, Gautam
296:
293:
288:
281:
278:
273:
266:
263:
258:
251:
248:
243:
239:
235:
231:
224:
221:
214:
210:
207:
205:
202:
201:
197:
195:
192:
188:
184:
182:
178:
174:
170:
166:
163:
162:closed source
155:
150:
147:
144:
140:
136:
133:
130:
126:
125:
124:
119:The algorithm
118:
116:
112:
110:
106:
102:
98:
90:
88:
86:
82:
75:
70:
68:
63:
57:Required form
56:
54:
52:
48:
44:
39:
37:
33:
29:
25:
21:
453:
446:
434:. Retrieved
425:
414:, retrieved
406:
399:
389:December 26,
387:. Retrieved
378:
361:
355:
328:
322:
305:
295:
289:. Macmillan.
286:
280:
271:
265:
256:
250:
233:
229:
223:
193:
189:
185:
159:
142:
138:
122:
113:
96:
94:
84:
77:
73:
71:
64:
60:
47:tractability
40:
32:Philip Wolfe
19:
18:
436:October 15,
274:. Springer.
236:: 101–111.
87:submatrix.
486:Categories
416:2014-03-31
215:References
466:cite book
198:See also
179:and the
128:program.
370:1888251
347:1960274
314:1438309
107:of its
368:
345:
335:
312:
458:(PDF)
411:(PDF)
472:link
438:2010
391:2008
333:ISBN
177:JuMP
169:GAMS
167:and
165:AMPL
72:The
30:and
238:doi
488::
468:}}
464:{{
366:MR
343:MR
341:.
310:MR
232:.
183:.
111:.
38:.
474:)
440:.
420:.
393:.
372:.
349:.
316:.
244:.
240::
234:8
143:x
139:x
97:n
85:F
80:i
78:F
74:D
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
