Mostrar el registro sencillo del ítem
On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T02:44:08Z | |
| dc.date.available | 2024-04-04T02:44:08Z | |
| dc.date.issued | 2000 | |
| dc.identifier.issn | 0030-364X | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191382 | |
| dc.description.abstractEn | Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear programming relaxation bound. The reformulation gives rise to an integer master problem, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm. There is a large class of integer programs that are well suited for this solution technique. In this paper, we propose to base the Dantzig-Wolfe decomposition of an integer program on the discretization of the integer polyhedron associated with a subsystem of constraints (as opposed to its convexification). This allows us to formulate the integrality restriction directly on the master variables and sets a theoretical framework for dealing with specific issues such as branching or the introduction of cutting planes in the master. We discuss specific branching schemes and their effect on the structure of the column generation subproblem. We give theoretical bounds on the complexity of the separation process and the extent of the modifications to the column generation subproblem. Our computational tests on the cutting stock problem and a generalisation -- the cutting strip problem -- show that, in practice, all fractional solutions can be eliminated using branching rules that preserve the tractability of the subproblem, but there is a trade-off. between branching efficiency and subproblem tractability. | |
| dc.language.iso | en | |
| dc.publisher | INFORMS | |
| dc.title.en | On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm | |
| dc.type | Article de revue | |
| bordeaux.journal | Operations Research | |
| bordeaux.page | 111-128 | |
| bordeaux.volume | 48 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 1 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00342641 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00342641v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Operations%20Research&rft.date=2000&rft.volume=48&rft.issue=1&rft.spage=111-128&rft.epage=111-128&rft.eissn=0030-364X&rft.issn=0030-364X&rft.au=VANDERBECK,%20Fran%C3%A7ois&rft.genre=article |
Archivos en el ítem
| Archivos | Tamaño | Formato | Ver |
|---|---|---|---|
|
No hay archivos asociados a este ítem. |
|||