Text

Consistency Cuts for Dantzig-Wolfe Reformulations

This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.70 No.5 September-October 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 2883-2905

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

INTEGER PROGRAMMING
THEORY
CUTTING PLANE/FACET
ALGORTIHMS

Info Detail Spesifik

https://doi.org/10.1287/opre.2021.2160

Pernyataan Tanggungjawab

Jens Vinther Clausen, Richard Lusby, Stefan Ropke

Versi lain/terkait

Lampiran Berkas

Komentar