High-multiplicity N-fold IP via configuration LP

• 成果类型: Article
• 署名作者: Knop, Dusan; Koutecky, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
• 署名单位: Czech Technical University Prague; Charles University Prague; Technion Israel Institute of Technology; Hamburg University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01882-9
• 发表日期: 2023
• 页码: 199-227
• 关键词: programming approach; integer; matrices; DECOMPOSITION; optimization; algorithms

摘要

N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems.