direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Multitype Integer Monoid Optimization and Scheduling

Dušan Knop (TU Berlin)


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. 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 are going to demonstrate the modeling power of MIMO on scheduling -- R|HM, rij, dij|Cmax with few job and machine types and (if time permits) we are going to discuss some other objectives such as sum of weighted completion times as well.



Dušan Knop
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras