ABSTRACT. Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving -- two broad and complex classes of heuristics -- as a multi-armed bandit problem. We verify our approach numerically and show consistent improvement over a state-of-the-art MIP solver across a wide range of instances.

ABSTRACT. In this work, we concentrate on the problem of finding a set of neurons in a trained neural network whose pruning leads to a marginal loss in accuracy. To this end, we introduce Optimizing ANN Architectures using Mixed-Integer Programming (OAMIP) to identify critical neurons and prune non-critical ones. The proposed OAMIP uses a Mixed-Integer Program (MIP) for assigning importance scores to each neuron in deep neural network architectures. The impact of neurons' simultaneous pruning on the main learning tasks guides the neurons' scores. By carefully devising the objective function of the MIP, we drive the solver to minimize the number of critical neurons (i.e., with high importance score) that maintain the overall accuracy of the trained neural network. Our formulation generalizes the recently considered lottery ticket optimization by identifying multiple "lucky" sub-networks resulting in an optimized architecture. This optimized architecture not only performs well on a single dataset but also generalizes across multiple ones upon retraining of network weights. Additionally, we present a scalable implementation of our pruning methodology by decoupling the importance scores across layers using auxiliary networks. Finally, we validate our approach experimentally, showing its ability to generalize on different datasets and architectures.

ABSTRACT. Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of cutoff measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.

ABSTRACT. We propose two pipelines for convex optimisation problems with uncertain parameters that aim to improve decision robustness by addressing the sensitivity of optimisation to parameter estimation. This is achieved by integrating uncertainty quantification (UQ) methods for supervised learning into the ambiguity sets for distributionally robust optimisation (DRO). The pipelines leverage learning to produce contextual/conditional ambiguity sets from side-information. The two pipelines correspond to different UQ approaches: i) explicitly predicting the conditional covariance matrix using deep ensembles (DEs) and Gaussian processes (GPs), and ii) sampling using Monte Carlo dropout, DEs, and GPs. We use i) to construct an ambiguity set by defining an uncertainty around the estimated moments to achieve robustness with respect to the prediction model. UQ ii) is used as an empirical reference distribution of a Wasserstein ball to enhance out of sample performance. DRO problems constrained with either ambiguity set are tractable for a range of convex optimisation problems. We propose data-driven ways of setting DRO robustness parameters motivated by either coverage or out of sample performance. These parameters provide a useful yardstick in comparing the quality of UQ between prediction models. The pipelines are computationally evaluated and compared with deterministic and unconditional approaches on simulated and real-world portfolio optimisation problems.

ABSTRACT. Real-world decision-making often involves working with many distinct objectives. However, as we consider a larger number of objectives, performance degrades rapidly and many instances become intractable. Our goal is to approximate high-dimensional Pareto frontiers within a reasonable amount of time. Our work is motivated by a problem in computational sustainability that evaluates the tradeoffs between various ecological impacts of hydropower dam proliferation in the Amazon river basin. The current state-of-the-art algorithm finds a good approximation of the Pareto frontier within hours for three-objective problems, but a six-objective problem cannot be solved in a reasonable amount of time. To tackle this problem, we developed two different approaches: an expansion method, which assembles Pareto-frontiers optimized with respect to subsets of the original set of criteria, and a compression method, which assembles Pareto-frontiers optimized with respect to compressed criteria, which are a weighted sum of multiple original criteria. Our experimental results show that the aggregation of the different methods can reliably provide good approximations of the true Pareto-frontiers in practice.

ABSTRACT. This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed many reconfiguration problems are known to be \PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts the breadth-first search by compressing the solution space using ZDDs, and finds a shortest transformation between two given feasible solutions if exists. Moreover, the proposed framework provides rich information on the solution space, such as the connectivity of the solution space and all feasible solutions reachable from a specified one. We demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate their performances.

ABSTRACT. In constraint satisfaction, pairwise consistency (PWC) is a well-known local consistency improving generalized arc consistency in theory but not often in practice. A popular approach to enforcing PWC enforces arc consistency on the dual encoding of the problem, allowing to reuse existing AC algorithms. In this paper, we explore the benefit of this simple approach in the optimization context of cost function networks and soft local consistencies. Using a dual encoding, we obtain an equivalent binary cost function network where enforcing virtual arc consistency achieves virtual PWC on the original problem. We experimentally observed that adding extra non-binary cost functions before the dual encoding results in even stronger bounds. Such supplementary cost functions may be produced by bounded variable elimination or by adding ternary zero-cost functions. Experiments on (probabilistic) graphical models, from the UAI 2022 competition benchmark, show a clear improvement when using our approach inside a branch-and-bound solver compared to the state-of-the-art.

ABSTRACT. Thanks to significant algorithmic advances in the field of computational bilevel optimization, today we can solve much larger and more complicated bilevel problems compared to what was possible two decades ago. In this talk, we will focus on one of the emerging and challenging classes of bilevel problems: bilevel optimization under uncertainty. We will discuss classical ways of addressing uncertainties in bilevel optimization using stochastic or robust optimization techniques. However, the sources of uncertainty in bilevel optimization can be much richer than for usual, single-level problems, since not only the problem’s data can be uncertain but also the (observation of the) decisions of the two players can be subject to uncertainty. Thus, we will also discuss bilevel optimization under limited observability, the area of problems considering only near-optimal decisions, and intermediate solution concepts between the optimistic and pessimistic cases.

The talk is based on the two articles by [1, 2].

References

[1] Yasmine Beck, Ivana Ljubic, Martin Schmidt, A Survey on Bilevel Optimization Under Uncertainty, European Journal of Operational Research, https://doi.org/10.1016/j.ejor.2023.01.008 (2023)

[2] Yasmine Beck, Ivana Ljubic, Martin Schmidt, A Brief Introduction to Robust Bilevel Optimization, SIAG/OPT Views and News, 30(2), (2023) https://siagoptimization.github.io/assets/views/ViewsAndNews-30-2.pdf

ABSTRACT. Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then known symmetry handling techniques can be applied. We demonstrate the effect of symmetry handling on different types of MISDPs. To this end, our symmetry detection routine is implemented in the state-of-the-art MISDP solver SCIP-SDP. We obtain speed-ups similar to the mixed-integer linear case.

ABSTRACT. A disjointly constrained bilinear program (DBLP) has various practical and industrial applications, e.g., in game theory, facility location, supply chain management, and multi-agent planning problems. Although earlier work has noted the equivalence of DBLP and mixed-integer linear programming (MILP) from an abstract theoretical perspective, a practical and exact closed-form reduction of a DBLP to a MILP has remained elusive. Such explicit reduction would allow us to leverage modern MILP solvers and techniques along with their solution optimality and anytime approximation guarantees. To this end, we provide the first constructive closed-form MILP reduction of a DBLP by extending the technique of symbolic variable elimination (SVE) to constrained optimization problems with bilinear forms. We apply our MILP reduction method to difficult DBLPs including XORs of linear constraints and show that we significantly outperform Gurobi. We also evaluate our method on a variety of synthetic instances to analyze the effects of DBLP problem size and sparsity w.r.t. MILP compilation size and solution efficiency.

ABSTRACT. This paper illustrates the application of graph invariants to break symmetries for graph search problems. The paper makes two contributions: (1) the use of higher dimensional graph invariants in symmetry breaking constraints; and (2) a novel technique to obtain symmetry breaking constraints by combining graph invariants. Experimentation demonstrates that the proposed approach applies to provide new results for the generation of a particular class of cubic graphs.

ABSTRACT. The introduction of Belief Propagation in Constraint Programming through the CP-BP framework makes possible the computation of an estimation of the probability that a given variable-value combination belongs to a solution. The availability of such marginal probability distributions, effectively ranking domain values, allows us to develop branching heuristics but also more generally to apply the concept of entropy to Constraint Programming. We explore how variable and problem entropy can improve how we solve combinatorial problems in the CP-BP framework. We evaluate our proposal on an extensive set of benchmark instances.

ABSTRACT. The Cumulative constraint is one of the most important global constraints, as it naturally arises in a variety of problems related to scheduling with limited resources. Devising fast propagation algorithms that run at every node of the search tree is critical to enable the resolution of a wide range of applications. Since its introduction, numerous propagation algorithms have been proposed, providing different tradeoffs between computational complexity and filtering power. Motivated by the impressive computational power that modern GPU provide, this paper explores the use of GPUs to speed up the propagation of the Cumulative constraint. The paper describes the development of a GPU-driven propagation algorithm, motivates the design choices, and provides solutions for several design challenges. The implementation is evaluated in comparison with state-of-the-art constraint solvers on different benchmarks from the literature. The results suggest that GPU-accelerated constraint propagators can be competitive by providing strong filtering in a reasonable amount of time.

ABSTRACT. This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the makespan of the schedule.

Exact solution methods incorporated within the framework of a two-stage robust optimization are proposed to solve the problem. We first prove that under particular conditions the robust two-machine permutation flow-shop scheduling problem can be solved in polynomial time by the well-known Johnson algorithm usually dedicated to the deterministic version. Then we tackle the general problem, for which we propose a column and constraint generation algorithm. We compare two versions of the algorithm. In the first version, a mixed-integer linear programming formulation is used for the master problem, the second version proposing, for the first time in such a decomposition approach, a constraint programming model.

The experimental results show the very good performance of the method based on the constraint programming formulation. We also notice that Johnson algorithm is surprisingly efficient for the robust version of the general problem.

ABSTRACT. We propose domain-independent dynamic programming (DIDP), a novel model-based paradigm for combinatorial optimization based on dynamic programming (DP). Model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) are considered to be a `holy-grail' of declarative programming: a user only needs to formulate a problem in order to solve it. In DP, a problem is formulated as a declarative model using recursive equations. However, little work has considered DP as a model-and-solve technique for combinatorial optimization. To this end, in DIDP, we separate modeling and solving in DP.

ABSTRACT. Counterfactual explanations play an important role in detecting bias and improving the explainability of data-driven classification models. A counterfactual explanation (CE) is a minimal perturbed data point for which the decision of the model changes. Most of the existing methods can only provide one CE, which may not be achievable for the user. In this work we derive an iterative method to calculate robust CEs, i.e. CEs that remain valid even after the features are slightly perturbed. To this end, our method provides a whole region of CEs allowing the user to choose a suitable recourse to obtain a desired outcome. We use algorithmic ideas from robust optimization and prove convergence results for the most common machine learning methods including logistic regression, decision trees, random forests, and neural networks. Our experiments show that our method can efficiently generate globally optimal robust CEs for a variety of common data sets and classification models.

ABSTRACT. We design an online contextual decision-making framework for a renewable energy source (RES) generator which has to trade, on a daily basis, its electricity in a wholesale market under uncertainty.

The RES generator, as a price-taker, needs to decide on an adequate level of energy production to offer in the day-ahead market which is cleared 12 to 36 hours ahead of the energy delivery. Regarding pricing incentives, two main regulatory pricing schemes are applied in the European market. At the delivery time, if there are deviations between the real production and the day-ahead committed energy, the generator will get rewarded or penalized in the single pricing scheme while only get penalized (at best does not reward) in the dual pricing scheme.

The main challenge for the RES is to decide the day-ahead offering strategy without full knowledge of these relevant problem parameters (e.g., real power output, system imbalance sign, day-ahead, and balancing prices) that would determine its profit.

Instead, the RES generator has available contextual information (e.g., seasonal information, calendar variables, aggregated time series forecast, including demand and renewable outputs, etc.) and past historical market outcomes that can be used to train different forecasting tools. Indeed, with this information, we show how relevant market variables, which up to know were considered unpredictable due to their volatile nature, can be forecasted with advanced machine learning techniques (LightGBM, CNN, RNN, LSTM, and Staked (LSTM+CNN)). These forecasts, combined with an adequate decision-making model (optimization-based) that accounts for uncertainty, can be used to improve the expected profit of the RES generator.

To this end, we propose to use a stochastic optimization setting, where the first-stage decisions represent the strategy in the day-ahead market, while the second-stage anticipates possible realizations of the uncertain parameters and corrective actions. Moreover, we make use of the point forecasts of the machine learning tools for the relevant parameters, together with past residuals and correlations, to generate a representative set of scenarios to be included in the stochastic optimization model.

Hence, on the one hand, instead of the separated predicting and decision-making in the “predict-then-optimize” paradigm, the “end-to-end” paradigm of contextual decision-making framework is adopted with a particular emphasis on integrated prediction and decision-making. On the other hand, online learning techniques are applied to ensure the aforementioned contextual decision-making framework adjusts to up-to-date information since the oldest samples may distort the evolving pattern in the recent information.

Several numerical simulations are implemented with real data to show the out-of-sample validity of the proposed approach to derive the optimal operation of RES generators. First, we study the predictive performance of the real power output, system imbalance signs, and market prices using contextual information. Then, adapting these forecasted inputs, we test and compare several benchmark prescriptive models with the data-driven stochastic setting proposed in this work. Specifically, we explore under which of the single and dual pricing schemes the RES can better benefit from the combination of the predictive and prescriptive model.