Semantics of MCDPs

Consider the following MCDP:

This is one way to describe it in MCDPL:

An MCDP is a family of optimization problems. Once we fix all the inputs, an MCDP becomes a standard optimization problem. For example, by fixing the input c=4, we obtain:

Note that whether the problem statement describes an MCDP is absolutely not obvious using the formula representation; it becomes obvious when writing the problem as a graph.


To solve an MCDP, one constructs a chain of antichains in the product poset of resources.

The animations below show the sequence of antichains being constructed to solve two variations of the same problem.