We study the steady-state expansion problem for potential-based flow networks. Constructing a cost-minimal network that admits a flow satisfying the underlying physical laws is a central problem in the design of gas, hydrogen, water, and electricity infrastructures. The physical behavior of such networks is governed by nonlinear relations between arc flows and the potential differences … Read more
Decision diagrams (DDs) have become a powerful tool for discrete optimization, supporting a wide range of algorithms that span cut-generation procedures, decomposition methods, and specialized branch-and-bound searches. Despite this growth, their adoption remains limited, partly because most existing DD code is tailored to a specific algorithm or application and is therefore hard to reuse. We … Read more
We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … Read more
Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further discuss an approach for handling rotation symmetries. In a computational … Read more
We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time … Read more
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 … Read more
The cone of positive semi-definite (SDP) matrices can be described by an infinite number of linear constraints. It is well-known that one can optimize over such a feasible area by standard Cutting Planes, but work on this idea remains a rare sight, likely due to its limited practical appeal compared to Interior Point Methods (IPMs). … Read more
This paper investigates the a-posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree’s branching … Read more
In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more
We consider Nash equilibrium problems with mixed-integer variables in which each player solves a mixed-integer optimization problem parameterized in the rivals’ strategies. We distinguish between standard Nash equilibrium problems (NEP), where the parameterization acts only on the players’ cost functions and generalized Nash equilibrium problems (GNEPs), where, additionally, the strategy spaces of the players may … Read more