  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 a 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 implicit notion explicit by observing that the set of all input
vectors decomposable into configurations forms a monoid, and solving the
configuration IP is the Monoid Decomposition problem. Motivated by
applications, we enrich this problem in two ways. First, sometimes each
configuration additionally has an objective value, yielding an optimization
problem of finding a "best" decomposition under the given objective. Second,
there are often different types of configurations for different types of
locations. The resulting problem is to optimize over decompositions of the
input multiplicity vector into configurations of several types, and we call it
Multitype Integer Monoid Optimization, or MIMO.
  We develop fast exact algorithms for various MIMO with few or many location
types and with various objectives. Our algorithms build on a novel proximity
theorem connecting 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.
