Introduction
Real-world decision-making often involves balancing conflicting objectives, such as cost versus quality. In combinatorial settings, the number of possible solutions grows exponentially, making it impossible to evaluate every option. This paper introduces a novel framework for solving multiobjective combinatorial optimization problems by leveraging Generalized Additive Independence (GAI) models. By representing complex preferences as structured "GAI nets," the authors provide an efficient message-passing algorithm to find exact Pareto-optimal solutions and a Fully Polynomial Time Approximation Scheme (FPTAS) for high-dimensional problems.
Structured Preferences: GAI Decompositions
Traditional models often assume "additive independence," where the value of one attribute is independent of others. However, in reality, dependencies are common—for instance, the utility of a specific processor depends on the motherboard it is paired with. GAI models bridge the gap between overly simplistic additive models and computationally intractable general models by breaking preferences into smaller, overlapping "factors" or "cliques."
The authors organize these cliques into a graphical structure called a GAI net. If this graph is a tree (or can be compiled into one), a "collect" algorithm—a form of dynamic programming—can propagate sets of non-dominated utility vectors across the network. This allows Pareto-optimality to be computed locally by passing "messages" of partial solutions up the tree.
Exact and Approximate Optimization
The exact algorithm constructs the global Pareto set by locally merging and filtering non-dominated vectors from cliques. However, because the Pareto set can still be exponentially large in the worst case, the authors introduce an FPTAS. This scheme uses $ε$-dominance to scale and round utility values into a logarithmic grid. This discretization ensures the algorithm returns a representative subset of solutions that are guaranteed to be within a factor of $(1+ε)$ of the true optimum.
Key Results and Insights
The efficiency of this approach is tied directly to the treewidth of the GAI net—a measure of how interconnected the attributes are.
- Performance and the Treewidth Bottleneck: In tests with 17 attributes, the exact algorithm solved problems in just 0.05 seconds when the treewidth was low (clique size 2). Conversely, high treewidth (17) led to timeouts, highlighting that the problem remains tractable only as long as interactions are relatively "thin."
- Drastic Compression: On pathological datasets where the exact Pareto set exceeded 1 million solutions, the FPTAS with a 10% error tolerance ($ε=0.1$) reduced the set to just 109 representative solutions in only 0.005 seconds.
- Scalability: The FPTAS maintained stable performance as the number of objectives increased from 2 to 10, demonstrating its robustness in high-dimensional trade-off spaces that typically paralyze standard exact solvers.
Conclusion
By exploiting the structural properties of GAI nets, this work provides a powerful tool for complex multiobjective problems. While the approach is limited by the treewidth of the interaction graph, the FPTAS offers a highly scalable alternative for real-world scenarios. Future research may explore integrating preference elicitation directly into the optimization loop or using search-based algorithms like A* to further prune the search space.
Summary updated