TL;DR
This paper provides the first systematic polyhedral study of Multiple Choice Polynomial Programming (MCPP), a generalization of 0-1 polynomial optimization where variables are constrained to "pick exactly one" from a set. The authors derive an explicit linear description (half-space representation) for these problems when the underlying structure is $\alpha$-acyclic and establish precise conditions for "lifting" known valid inequalities into this more complex constrained space.
What Problem Does This Paper Address?
In discrete optimization, we often deal with 0-1 (Boolean) variables. A common task is Pseudo-Boolean Optimization (PBO), where we minimize a polynomial function of these variables. However, real-world problems often come with "multiple choice" constraints—for example, in a scheduling task, you might have five possible time slots for a meeting, but you must choose exactly one.
While the "multilinear polytope" (the convex hull of feasible points for unconstrained 0-1 polynomial programs) has been studied extensively, the version with these "one-of-many" constraints—termed the MCPP polytope—has remained largely unexplored. This paper fills that gap, providing a mathematical foundation for solving MCPP problems using linear programming relaxations and branch-and-cut algorithms.
Methods
The authors represent the structure of the polynomial and its constraints using hypergraphs, where nodes represent variable sets and hyperedges represent the monomials (products of variables) in the objective function.
Key technical approaches include:
- Linearization: Replacing non-linear product terms (like $x_1 x_2 x_3$) with new linear variables ($w_J$) and adding "production constraints" to ensure they behave correctly.
- Join Trees and $\alpha$-acyclicity: The authors focus on $\alpha$-acyclic hypergraphs. These are structures that can be organized into a "join tree," a roadmap that allows the problem to be decomposed into smaller, manageable pieces.
- Inductive Proofs: They prove the half-space representation by inducting on the number of hyperedges, using a "decomposability property" to stitch together the descriptions of sub-hypergraphs.
- Facet Lifting: They take known "facet-inducing" inequalities from the simpler unconstrained multilinear polytope and use a mathematical "flipping" technique to determine exactly when these remain strong (facet-defining) for the MCPP polytope.
Datasets
Not discussed in the paper. This is a theoretical mathematical study focused on proving structural properties and representations of polytopes; it does not include empirical tests on benchmark datasets.
Key Insights and Ideas
- Structural Relaxation: Interestingly, while the unconstrained multilinear polytope often requires a stricter property called $\gamma$-acyclicity for a simple linear description, the MCPP polytope achieves a similar explicit representation under the more general $\alpha$-acyclicity.
- The Power of Decomposability: The authors show that if a hypergraph can be split at a "separator" that is itself a hyperedge (or a subset of one), the MCPP polytope is simply the intersection of the polytopes of its parts.
- Precise Lifting Conditions: Lifting an inequality isn't a "one-size-fits-all" process. The authors found a necessary and sufficient condition (Theorem 1.2) based on the size of the subsets chosen from each partition. Specifically, for an inequality to remain a "facet" (a high-dimensional face of the polytope), the chosen subsets must either have exactly one element or be exactly one element short of the full partition, depending on the specific structure of the original inequality.
Key Results
- Theorem 1.1 (Half-space Representation): Provides the complete set of linear equations and inequalities that define the MCPP polytope for $\alpha$-acyclic hypergraphs.
- Polynomial Time Solvability: The authors demonstrate that if the hypergraph is $\alpha$-acyclic and its "rank" (the maximum number of variables in a product) is bounded, MCPP can be solved in polynomial time using linear programming.
- Generalization of PBO: The results successfully generalize known properties of Pseudo-Boolean Optimization (the "binary" case) to the "$|I|$-ary" multiple-choice case.
- Unified Framework: Their lifting results encompass and generalize several specific cases previously found in the literature, such as those related to the bipartite Boolean quadric polytope.
Limitations and Future Work
- General Hypergraphs: The explicit half-space representation is only provided for $\alpha$-acyclic hypergraphs. For general, cyclic structures, the full description remains an open challenge.
- Separation Algorithms: While the paper identifies valid inequalities, it does not provide "separation algorithms"—computational methods to quickly find which of these inequalities are violated during a solver's execution.
- Affine Hull Complexity: The authors note that determining the implicit equalities (the affine hull) for general hypergraphs is still difficult and suggest that adding "dummy" hyperedges to make a graph "downward-closed" might be a path forward.
- Cycle-Free Degrees: The authors suggest exploring even weaker forms of acyclicity, such as "cycle-free" hypergraphs, to see if these results can be pushed even further.
Summary updated