Many optimization problems are made more challenging due to multiple, conflicting criteria. The subjective nature of balancing these criteria motivates techniques for inverse optimization. This study establishes foundations for an exact representation of the inverse feasible region of a multiobjective integer program. We provide the first insights into its exact structure, as well as two well-structured outer approximations to better capture its odd form. The first approximation is based on incomparability (where no solution should dominate another), and the second is based on supportedness (where some solutions should be optimal for a weighted sum scalarization). We include novel visualization tools to establish geometric intuition of the approximations’ structure. We define several convexity-related subproblems, including convex cores and half-space coverings.
Citation
Perini, Tyler et. al. "On the Structure of the Inverse-Feasible Region of a Multiobjective Integer Program". July 2025.