Benders decomposition with scaled cuts for multistage stochastic mixed-integer programs

We consider Benders decomposition algorithms for multistage stochastic mixed-integer programs (SMIPs) with general mixed-integer decision variables at every node in the scenario tree. We derive a hierarchy of convex polyhedral lower bounds for the value functions and expected cost to-go functions in multistage SMIPs using affine parametric cutting planes in extended spaces for the feasible … Read more

An Extended Validity Domain for Constraint Learning

We consider embedding a predictive machine-learning model within a prescriptive optimization problem. In this setting, called constraint learning, we study the concept of a validity domain, i.e., a constraint added to the feasible set, which keeps the optimization close to the training data, thus helping to ensure that the computed optimal solution exhibits less prediction … Read more

Extended Formulations for Control Languages Defined by Finite-State Automata

Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, for these and many similar types of constraints, it is possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via extended formulations. In … Read more

Heuristic Methods for Mixed-Integer, Linear, and Γ-Robust Bilevel Problems

Due to their nested structure, bilevel problems are intrinsically hard to solve–even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel … Read more

Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased

Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include a given set of elements in the solution of their combinatorial problem. If the set of required elements defines a complete follower solution, the inverse combinatorial problem is solvable in polynomial time as soon as … Read more

A proof system for certifying symmetry and optimality reasoning in integer programming

We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more

Learning Optimal Classification Trees Robust to Distribution Shifts

We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time … Read more

A Computational Study for Piecewise Linear Relaxations of Mixed-Integer Nonlinear Programs

Solving mixed-integer nonlinear problems by means of piecewise linear relaxations can be a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems. In this work, we compare different reformulations in terms … Read more

A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more

Robust Optimization Under Controllable Uncertainty

Applications for optimization with uncertain data in practice often feature a possibility to reduce the uncertainty at a given query cost, e.g., by conducting measurements, surveys, or paying a third party in advance to limit the deviations. To model this type of applications we introduce the concept of optimization problems under controllable uncertainty (OCU). For … Read more