Optimization problems that involve multiple, conflicting criteria lead to a set of efficient solutions, and when there are discrete decisions, some solutions may be unsupported. Applications where it is difficult to estimate the parameters for criteria motivate inverse optimization techniques. We provide a theoretical analysis of the set of (unknown) objective parameters which lead to a (known) efficient subset of feasible solutions, known as the inverse-feasible region, of a multiobjective integer program. We provide insights into its structure by means of two well-structured outer approximations that help to capture its odd form. The first approximation is based on supportedness (where some solutions should be optimal for a weighted sum scalarization), and the second is based on incomparability (where no solution should dominate another). We include visualizations for the two-variable-two-objective case which help establish geometric intuition for the structure of these sets. As part of the theoretical contributions, several convexity-related subproblems are introduced, including convex cores and half-space coverings. Concluding remarks outline the remaining gaps in giving an exact representation.
Citation
Perini, Tyler et. al. "On the Structure of the Inverse-Feasible Region of a Multiobjective Integer Program". July 2026.