A Polynomial-Time Inner Approximation Algorithm for Multi-Objective and Parametric Optimization

This paper presents a new polynomial-time adaptive algorithm based on Csirmaz's skeleton method for constructing convex approximation sets in multi-objective mixed-integer linear programs, which outperforms the current state-of-the-art approach by Helfrich et al. (2024) on various benchmark problems.

The Gist

The Big Picture: The "Impossible" Menu

Imagine you are running a restaurant that serves the most complex, multi-course meals in the world. You have three goals for every dish:

1. Taste (Make it delicious).
2. Health (Make it nutritious).
3. Cost (Make it cheap).

The problem is, these goals fight each other. The most delicious dish might be full of sugar (bad for health) or made of gold leaf (too expensive). The cheapest dish might taste like cardboard.

In math, this is called Multi-Objective Optimization. The "perfect" list of all possible dishes that balance these three goals is called the Pareto Front.

The Catch: For complex problems (like planning a global supply chain or a military strategy), this list of "perfect" dishes is so huge that it's impossible to write down. It could take longer than the age of the universe to calculate every single option. It's like trying to count every grain of sand on a beach to find the perfect one.

The Old Way: The Grid Trap

For years, mathematicians tried to solve this by drawing a giant grid over the map of all possible dishes.

• They would divide the "Taste/Health/Cost" map into tiny squares.
• They would pick one dish from every square to represent that area.

The Problem: This grid is like a fishing net with holes so small you catch every single grain of sand. It's too slow, and the numbers get so messy that computers get confused (like trying to measure a mountain with a ruler meant for a grain of rice).

The New Way: The "Convex Hull" Shortcut

The authors of this paper (Levin Nemesch, Stefan Ruzika, et al.) came up with a smarter way. Instead of trying to catch every grain of sand, they decided to build a flexible, stretchy balloon around the best dishes.

They call this a Convex Approximation Set.

The Analogy:
Imagine the "Perfect Dishes" are scattered across a dark room.

• The Old Method: You turn on a floodlight and try to photograph every single speck of dust. It takes forever.
• The New Method: You throw a giant, stretchy rubber sheet (a balloon) over the specks. You don't need to see every speck; you just need the sheet to cover them all. If you stretch the sheet just a tiny bit (by a factor of $1+\epsilon$), you can cover the whole room with just a few points where you pin the sheet down.

Any point inside that balloon is "good enough." You don't need the exact perfect dish; you just need a dish that, when mixed with other dishes on your menu, creates a version that is almost as good as the perfect one.

How Their Algorithm Works: The "Skeleton"

The paper introduces a new algorithm (let's call it IAA) that builds this rubber sheet efficiently.

1. Start Small: They start with just one dish (one point) and draw a tiny balloon around it.
2. The "Oracle" (The Taste Tester): They ask a "Taste Tester" (a computer program): "Is there a dish out there that is better than this balloon?"
   • If the tester says "No," they are done. The balloon covers everything.
   • If the tester says "Yes, here is a better dish," they add that dish to their list and stretch the balloon to include it.
3. Repeat: They keep stretching the balloon until it covers the whole "room" of possibilities.

The Magic Trick:
The authors realized they could use a technique from geometry called the "Skeleton Algorithm." Instead of checking a rigid grid, their algorithm is adaptive. It only looks where it needs to look. It's like a hiker who only checks the path ahead, rather than trying to map the whole mountain before taking a single step.

Why Is This Better? (The Race Results)

The authors tested their new algorithm against the current "champion" algorithm (by Helfrich et al., 2024).

• The Champion (OAA): It's very careful. It checks a lot of spots to make sure the balloon is perfectly tight. It finds a very accurate list, but it takes a long time.
• The New Contender (IAA): It's faster and smarter. It builds the balloon quickly.
  • Result: On problems like the Knapsack Problem (packing a bag with the most value) and the Traveling Salesman Problem (finding the shortest route), the new algorithm was much faster.
  • Trade-off: The new algorithm's balloon is slightly "looser" (it approximates a bit more), but it gets the job done in seconds instead of hours.

Real-World Impact

Why does this matter?

1. Parametric Optimization: This is useful for problems where you change the rules on the fly. For example, "If I want to save 10% more money, how does my route change?" The new algorithm can answer these "What if?" questions instantly.
2. Mixed-Integer Problems: These are problems where you have to make whole-number decisions (like "buy 3 trucks, not 3.5 trucks"). This is notoriously hard, but the new algorithm handles it well.

The Bottom Line

The authors built a polynomial-time inner approximation algorithm.

• Polynomial-time: It's fast enough to be useful in the real world.
• Inner Approximation: It builds a shape inside the perfect solution set that covers almost everything.
• Grid-Agnostic: It doesn't rely on the clumsy, slow grid method.

In short: They found a way to draw a map of a complex, impossible territory by only checking the most important landmarks, rather than trying to count every single tree. It's faster, it's flexible, and it gets the job done.

Technical Summary

1. Problem Statement

The paper addresses the challenge of solving Multi-Objective Mixed-Integer Linear Programs (MOMILPs).

• The Core Difficulty: In multi-objective optimization, the goal is to find the non-dominated set (Pareto front). However, for MOMILPs, this set can be exponentially large or even infinite. Computing the exact set is often NP-hard or intractable.
• The Approximation Goal: Instead of finding the exact set, the authors aim to compute a $(1+\epsilon)$-convex approximation set.
  • A set $R$ is a $(1+\epsilon)$-convex approximation set if, for every feasible solution $x$, there exists a point in the convex hull of the images of $R$ that $(1+\epsilon)$-approximates the image of $x$.
  • This concept relaxes the requirement that the approximating point must be an actual image of a solution, allowing it to be a convex combination of images.
• Limitations of Existing Methods: Previous state-of-the-art algorithms (e.g., Helfrich et al., 2024) rely on constructing a grid in the weight space (dual space). While adaptive, these methods still interact with grid structures that can lead to numerical instability and inefficiency in practice.

2. Methodology

The authors propose a new algorithm (IAA) based on inner polyhedral approximation and adaptive oracle calls, avoiding the explicit construction of the weight-space grid used in previous approaches.

Key Algorithmic Components:

1. Inner Approximation Framework:

   • The algorithm is derived from the skeleton algorithm for polyhedral inner approximation (Csirmaz, 2021), which is a generalization of the dual Benson algorithm.
   • It maintains an inner approximation polyhedron $A^{(k)}$ (initially a single point plus the non-negative orthant) that is contained within the Edgeworth-Pareto hull ($Y^+$) of the non-dominated set.
   • The goal is to iteratively refine $A^{(k)}$ until it contains the scaled hull $Y^+_{1+\epsilon} = \{(1+\epsilon)v \mid v \in Y^+\}$.

2. Adaptive Oracle Calls (The Core Innovation):

   • Instead of checking all points in a grid, the algorithm iterates through the facet-supporting halfspaces of the current polyhedron $A^{(k)}$.
   • For a halfspace $H = \{z \mid w^T z \geq c\}$, the algorithm does not call the oracle on $H$. Instead, it calls a plane separating oracle on a modified halfspace:
     $$H_{1+\epsilon} = \{z \mid (1+\epsilon)w^T z \geq c\}$$
   • Logic: If the oracle returns a solution $x^*$ such that its image $f(x^*)$ is not in $H_{1+\epsilon}$, it implies that $(1+\epsilon)f(x^*)$ is not in $H$. This allows the algorithm to detect if the current polyhedron fails to cover the scaled hull $Y^+_{1+\epsilon}$.
   • If a solution is found, the polyhedron is updated: $A^{(k+1)} = \text{conv}(\{f(x^*)\} \cup A^{(k)}) + \mathbb{R}^d_{\geq 0}$.

3. Oracles and Scalarization:

   • The algorithm requires a plane separating oracle.
   • Exact Case: If the Weighted Sum Scalarization (WS) can be solved exactly, the oracle solves $\min w^T f(x)$.
   • Approximate Case: If WS is NP-hard (e.g., TSP, Knapsack), the algorithm can use an $\alpha$-approximation algorithm for WS. Theoretically, this results in an $\alpha(1+\epsilon)$-convex approximation set.
   • This flexibility allows the method to handle problems where exact scalarization is impossible but approximate scalarization is polynomial-time.

4. Grid-Agnostic Nature:

   • Unlike previous methods, IAA does not construct or iterate over a grid in the weight space. It only interacts with specific halfspaces generated by the facets of the current approximation polyhedron. This avoids the numerical issues associated with high-precision grid encoding.

3. Key Contributions

• New Algorithm (IAA): A polynomial-time algorithm for computing convex approximation sets that is grid-agnostic. It adapts the exact inner approximation skeleton to the approximation setting.
• Theoretical Guarantees:
  • Proves that if the oracle runs in polynomial time, the algorithm is a cFPTAS (convex Fully Polynomial-Time Approximation Scheme) or cPTAS depending on the oracle's capabilities.
  • Shows that the number of solutions returned is bounded by $O(\text{poly}(\langle I \rangle, \epsilon^{-1}))$.
  • Demonstrates that using an $\alpha$-approximate oracle yields an $\alpha(1+\epsilon)$-approximation.
• Handling Combinatorial Problems: The method extends to problems like the Multi-Objective Knapsack and Traveling Salesman Problem (TSP) by utilizing existing approximation algorithms for their weighted sum scalarizations.

4. Computational Results

The authors conducted a computational study comparing IAA against the state-of-the-art algorithm OAA (Helfrich et al., 2024) on three problem types:

1. Multi-Objective Assignment Problem (AP) (solved exactly).
2. Multi-Objective Knapsack Problem (KP) (approximated via greedy).
3. Multi-Objective Symmetric Metric TSP (approximated via Christofides' algorithm).

Key Findings:

• Running Time: IAA is significantly faster than OAA across all instance types and sizes. In many cases, OAA hits the 1-hour time limit while IAA finishes in seconds.
• Solution Set Size: IAA returns far fewer solutions than OAA. For example, in Knapsack problems, IAA often returns 1–5 solutions, whereas OAA's set size grows with the instance size.
• Accuracy vs. Efficiency Trade-off:
  • OAA produces sets with a lower $\epsilon$-convex indicator (closer to the theoretical target), meaning it is more "accurate" in terms of the approximation factor.
  • IAA produces sets with a higher $\epsilon$-convex indicator (closer to the theoretical bound $\alpha(1+\epsilon)$), meaning it utilizes the allowed approximation margin more aggressively to gain speed.
  • Conclusion: IAA offers a superior trade-off for practitioners who prioritize speed and smaller solution sets over strict minimization of the approximation factor.
• Scalability: IAA scales much better with the number of objectives (tested up to 6 objectives in AP instances), whereas OAA frequently fails to terminate within the time limit for higher dimensions.
• Representation Quality: When evaluated as "representations" (using metrics like Coverage Error and Hypervolume Ratio), OAA performs slightly better for a fixed $\epsilon$. However, IAA with a tighter $\epsilon$ (e.g., 0.01) often achieves comparable representation quality to OAA with a looser $\epsilon$ (0.1) but in significantly less time.

5. Significance

• Practical Viability: The paper demonstrates that grid-agnostic approaches are not only theoretically sound but practically superior for solving multi-objective mixed-integer problems.
• Parametric Optimization: Since convex approximation sets are equivalent to parametric approximation sets, this algorithm provides a powerful new tool for parametric optimization (optimizing linear combinations of objectives), extending its utility to non-convex and combinatorial domains.
• Robustness: By avoiding the explicit construction of high-precision grids, the algorithm mitigates numerical instability issues common in fixed-precision arithmetic, making it more robust for real-world applications.
• Flexibility: The ability to plug in approximate scalarization oracles makes the algorithm applicable to a broader range of NP-hard multi-objective problems where exact scalarization is infeasible.

In summary, the paper presents a breakthrough in multi-objective optimization by shifting from grid-based methods to an adaptive, inner-approximation approach that is faster, more scalable, and numerically more stable, while maintaining rigorous theoretical approximation guarantees.