A feasible rounding approach for mixed-integer optimization problems

Christoph Neumann (), Oliver Stein () and Nathan Sudermann-Merx ()
Additional contact information
Christoph Neumann: Karlsruhe Institute of Technology (KIT)
Oliver Stein: Karlsruhe Institute of Technology (KIT)
Nathan Sudermann-Merx: BASF Business Services GmbH

Computational Optimization and Applications, 2019, vol. 72, issue 2, No 2, 309-337

Abstract: Abstract We introduce granularity as a sufficient condition for the consistency of a mixed-integer optimization problem, and show how to exploit it for the computation of feasible points: For optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixed-integer problem. Thus, the resulting feasible rounding approach is deterministic and even efficient, i.e., it computes feasible points in polynomial time. The optimization problems appearing in the feasible rounding approaches have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics, as long as the problem is granular. For instance, the computational cost of our approach always corresponds to merely a single step of the feasibility pump. A computational study on optimization problems from the MIPLIB libraries demonstrates that granularity may be expected in various real world applications. Moreover, a comparison with Gurobi indicates that state of the art software does not always exploit granularity. Hence, our algorithms do not only possess a worst-case complexity advantage, but can also improve the CPU time needed to solve problems from practice.

Keywords: Rounding; Granularity; Inner parallel set; Consistency; 90C11; 90C10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-018-0042-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:72:y:2019:i:2:d:10.1007_s10589-018-0042-y

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-018-0042-y

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().