Text

Robust Mixed 0-1 Programming and Submodularity

We study the solution set of the robust continuous 0-1 knapsack problem with a single unrestricted continuous variable. Using the submodularity of the cardinality-constrained robust 0-1 knapsack set function, we identify extended polymatroid inequalities that can be used as cutting planes in a branch-and-cut algorithm. We propose a polynomial-time separation algorithm for the most violated extended polymatroid inequality. We prove that the convex hull of the feasible solutions to the robust continuous 0-1 knapsack problem can be described completely by extended polymatroid inequalities and bound inequalities. Additionally, we propose a polynomial-time algorithm for the robust continuous 0–1 knapsack problem itself. We report computational results that show the effectiveness of the proposed extended polymatroid inequalities.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION; Vol.3 No.2 Spring 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 183 - 199

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

ROBUST OPTIMIZATION
VALID INEQUALITIES
SUBMODULAR FUNCTION

Info Detail Spesifik

https://doi.org/10.1287/ijoo.2019.0042

Pernyataan Tanggungjawab

Seulgi Joung, Sungsoo Park

Versi lain/terkait

Lampiran Berkas

Komentar