Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs.
Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial.
We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane techniques directly in the binary variable space.
At the core lies a multipartite generalization of the bipartite implication polytope, capturing conditional relations between several groups of multiple-choice variables and an implied selection.
We analyze the polyhedral structure of this polytope and a natural set-valued variant, deriving a unifying family of valid inequalities and characterizing all nontrivial facets.
Building on this theory, we design a generic separation algorithm and embed it into standard multiple-choice and incremental piecewise-linear mixed-integer relaxations of mixed-integer nonlinear programs.
We further exploit structure in the underlying nonlinearities to precompute strong cuts for relevant application classes such as pooling problems and Gaussian processes.
Extensive computational experiments on MINLPLib instances demonstrate that the proposed cuts significantly tighten the linear relaxations and thereby reduce solution times.