TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Tue, 31 Jan 2023 11:18:29 GMT2023-01-31T11:18:29Z5031- Multitype integer monoid optimization and applicationshttp://hdl.handle.net/11420/5005Title: Multitype integer monoid optimization and applications
Authors: Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Abstract: Configuration integer programs (IP) have been key in the design of algorithms for NP-hard
high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 1961].
Configuration IPs have one variable for each possible configuration, which describes a placement
of items into a location, and whose value corresponds to the number of locations with that
placement. In high multiplicity problems items come in types, and are represented succinctly
by a vector of multiplicities; solving the configuration IP then amounts to deciding whether the
input vector of multiplicities of items of each type can be decomposed into a given number of
configurations.
We make this typically implicit notion explicit by observing that the set of all input vectors
which can be decomposed into configurations forms a monoid of configurations, and the problem
corresponding to solving the configuration IP is the Monoid Decomposition problem. Then,
motivated by applications, we enrich this problem in two ways. First, in certain problems each
configuration additionally has an objective value, and the problem becomes an optimization
problem of finding a “best” decomposition under the given objective. Second, there are often
different types of configurations derived from different types of locations. The resulting problem
is then to optimize over decompositions of the input multiplicity vector into configurations of
several types, and we call it Multitype Integer Monoid Optimization, or simply MIMO.
We develop fast exact (exponential-time) algorithms for various MIMO with few or many
location types and with various objectives. Our algorithms build on a novel proximity theorem
which connects the solutions of a certain configuration IP to those of its continuous relaxation.
We then cast several fundamental scheduling and bin packing problems as MIMOs, and thereby
obtain new or substantially faster algorithms for them.
We complement our positive algorithmic results by hardness results which show that, under
common complexity assumptions, the algorithms cannot be extended into more relaxed regimes.
Mon, 16 Sep 2019 00:00:00 GMThttp://hdl.handle.net/11420/50052019-09-16T00:00:00Z
- Parameterized complexity of configuration integer programshttp://hdl.handle.net/11420/11096Title: Parameterized complexity of configuration integer programs
Authors: Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Abstract: Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we showcase the implications of these results to bin-packing and facility-location-like problems.
©2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND
Mon, 15 Nov 2021 00:00:00 GMThttp://hdl.handle.net/11420/110962021-11-15T00:00:00Z
- High multiplicity N-fold IP via configuration LPhttp://hdl.handle.net/11420/13427Title: High multiplicity N-fold IP via configuration LP
Authors: Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Abstract: 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-multiplicity N-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.
Wed, 21 Sep 2022 00:00:00 GMThttp://hdl.handle.net/11420/134272022-09-21T00:00:00Z