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.