Text

Presolving for Mixed-Integer Semidefinite Optimization

This paper provides a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The methods considered include adding linear constraints, deriving bounds relying on 2 × 2 minors of the semidefinite constraints, tightening of variable bounds based on solving a semidefinite program with one variable, and scaling of the matrices in the semidefinite constraints. Tightening the bounds of variables can also be used in a node presolving step. Along the way, we discuss how to solve semidefinite programs with one variable using a semismooth Newton method and the convergence of iteratively applying bound tightening. We then provide an extensive computational comparison of the different presolving methods, demonstrating their effectiveness with an improvement in running time of about 22% on average. The impact depends on the instance type and varies across the methods.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION; Vol. 5, No. 2, Spring 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 131-154

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PROPAGATION
PRESOLVING
BOUND TIGHTENING
MIXED-INTEGER SEMIDEFINITE OPTIMIZATION

Info Detail Spesifik

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

Pernyataan Tanggungjawab

Frederic Matter, Marc E. Pfetsch

Versi lain/terkait

Lampiran Berkas

Komentar