Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLPs). These relaxations can be obtained by using recursive McCormick linearizations (RMLs), by which an MLP is linearized by iteratively substituting bilinear products with artificial variables and constraints. This article introduces a systematic approach to identifying RMLs. We focus on identifying RMLs with a small number of artificial variables and strong LP bounds. We present a novel mechanism for representing all the possible RMLs, which we use to design an exact mixed-integer programming (MIP) formulation to identify minimum-size RMLs; this problem is NP-hard in general, but we show that it is fixed-parameter tractable if each monomial is composed of at most three variables. Moreover, we explore the structural properties of our formulation to derive an exact MIP model that identifies RMLs of a given size with the best-possible LP relaxation bound. We test our algorithms by conducting numerical experiments on a large collection of MLPs. Numerical results indicate that the RMLs obtained with our algorithms can be significantly smaller than those derived from heuristic or greedy approaches, leading, in many cases, to tighter LP relaxation bounds. Moreover, our linearization strategies can be used to reformulate MLPs as quadratically constrained programs (QCPs), which can then be efficiently solved using state-of-the-art solvers for QCPs. This QCP-based solution approach is highly beneficial for hard MLP instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

We study stochastic optimization problems with objective function given by the expectation of the maximum of two linear functions defined on the component random variables of a multivariate Gaussian distribution. We consider random variables that are arbitrarily correlated, and we show that the problem is NP-hard even if the space of feasible solutions is unconstrained. We exploit a closed-form expression for the objective function from the literature to construct a cutting-plane algorithm for a highly nonlinear function, which includes the evaluation of the cumulative distribution function and probability density function of a standard normal random variable with decision variables as part of the arguments. To exhibit the model’s applicability, we consider two featured applications. The first is daily fantasy sports, where the algorithm identifies entries with positive returns during the 2018–2019 National Football League season. The second is a special case of makespan minimization for two parallel machines and jobs with uncertain processing times; for the special case where the jobs are uncorrelated, we prove the equivalence between its deterministic and stochastic versions and show that our algorithm can deliver a constant-factor approximation guarantee for the problem. The results of our computational evaluation involving synthetic and real-world data suggest that our discretization and upper bounding techniques lead to significant computational improvements and that the proposed algorithm outperforms suboptimal solutions approaches. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1259 .

We study optimization problems where the objective function is modeled through feedforward neural networks with rectified linear unit (ReLU) activation. Recent literature has explored the use of a single neural network to model either uncertain or complex elements within an objective function. However, it is well known that ensembles of neural networks produce more stable predictions and have better generalizability than models with single neural networks, which motivates the investigation of ensembles of neural networks rather than single neural networks in decision-making pipelines. We study how to incorporate a neural network ensemble as the objective function of an optimization model and explore computational approaches for the ensuing problem. We present a mixed-integer linear program based on existing popular big-M formulations for optimizing over a single neural network. We develop a two-phase approach for our model that combines preprocessing procedures to tighten bounds for critical neurons in the neural networks with a Lagrangian relaxation-based branch-and-bound approach. Experimental evaluations of our solution methods suggest that using ensembles of neural networks yields more stable and higher quality solutions, compared with single neural networks, and that our optimization algorithm outperforms (the adaption of) a state-of-the-art approach in terms of computational time and optimality gaps. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework represents these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest-path problem in an auxiliary network. We design techniques for exploiting network models in order to accelerate the identification of the Pareto frontier, most notably a number of operations to simplify the network by removing nodes and arcs while preserving the set of nondominated solutions. We show that the proposed framework yields orders-of-magnitude performance improvements over existing state-of-the-art algorithms on five problem classes containing both linear and nonlinear objective functions. Summary of Contribution: Multiobjective optimization has a long history of research with applications in several domains. Our paper provides an alternative modeling and solution approach for multiobjective discrete optimization problems by leveraging graphical structures. Specifically, we encode the decision space of a problem as a layered network and propose graph reduction operators to preserve only solutions whose image are part of the Pareto frontier. The nondominated solutions can then be extracted through shortest-path algorithms on such a network. Numerical results comparing our method with state-of-the-art approaches on several problem classes, including the knapsack, set covering, and the traveling salesperson problem (TSP), suggest orders-of-magnitude runtime speed-ups for exactly enumerating the Pareto frontier, especially when the number of objective functions grows.

In the bin-packing problem with minimum color fragmentation (BPPMCF), we are given a fixed number of bins and a collection of items, each associated with a size and a color, and the goal is to avoid color fragmentation by packing items with the same color within as few bins as possible. This problem emerges in areas as diverse as surgical scheduling and group event seating. We present several optimization models for the BPPMCF, including baseline integer programming formulations, alternative integer programming formulations based on two recursive decomposition strategies that utilize decision diagrams, and a branch-and-price algorithm. Using the results from an extensive computational evaluation on synthetic instances, we train a decision tree model that predicts which algorithm should be chosen to solve a given instance of the problem based on a collection of derived features. Our insights are validated through experiments on the aforementioned applications on real-world data. Summary of Contribution: In this paper, we investigate a colored variant of the bin-packing problem. We present and evaluate several exact mixed-integer programming formulations to solve the problem, including models that explore recursive decomposition strategies based on decision diagrams and a set partitioning model that we solve using branch and price. Our results show that the computational performance of the algorithms depends on features of the input data, such as the average number of items per bin. Our algorithms and featured applications suggest that the problem is of practical relevance and that instances of reasonable size can be solved efficiently.

Artificial Intelligence (AI) has been used extensively in automatic decision making in a broad variety of scenarios, ranging from credit ratings for loans to recommendations of movies. Traditional design guidelines for AI models focus essentially on accuracy maximization, but recent work has shown that economically irrational and socially unacceptable scenarios of discrimination and unfairness are likely to arise unless these issues are explicitly addressed. This undesirable behavior has several possible sources, such as biased datasets used for training that may not be detected in black-box models. After pointing out connections between such bias of AI and the problem of induction, we focus on Popper's contributions after Hume's, which offer a logical theory of preferences. An AI model can be preferred over others on purely rational grounds after one or more attempts at refutation based on accuracy and fairness. Inspired by such epistemological principles, this paper proposes a structured approach to mitigate discrimination and unfairness caused by bias in AI systems. In the proposed computational framework, models are selected and enhanced after attempts at refutation. To illustrate our discussion, we focus on hiring decision scenarios where an AI system filters in which job applicants should go to the interview phase.

An important feature of cloud computing is its elasticity, that is, the ability to have resource capacity dynamically modified according to the current system load. Auto-scaling is challenging because it must account for two conflicting objectives: minimising system capacity available to users and maximising QoS, which typically translates to short response times. Current auto-scaling techniques are based solely on load forecasts and ignore the perception that users have from cloud services. As a consequence, providers tend to provision a volume of resources that is significantly larger than necessary to keep users satisfied. In this article, we propose a scheduling algorithm and an auto-scaling triggering technique that explore user patience in order to identify critical times when auto-scaling is needed and the appropriate volume of capacity by which the cloud platform should either extend or shrink. The proposed technique assists service providers in reducing costs related to resource allocation while keeping the same QoS to users. Our experiments show that it is possible to reduce resource-hour by up to approximately 8% compared to auto-scaling based on system utilisation.

Auto-scaling is a key feature in clouds responsible for adjusting the number of available resources to meet service demand. Resource pool modifications are necessary to keep performance indicators, such as utilisation level, between user-defined lower and upper bounds. Auto-scaling strategies that are not properly configured according to user workload characteristics may lead to unacceptable QoS and large resource waste. As a consequence, there is a need for a deeper understanding of auto-scaling strategies and how they should be configured to minimise these problems. In this work, we evaluate various auto-scaling strategies using log traces from a production Google data centre cluster comprising millions of jobs. Using utilisation level as performance indicator, our results show that proper management of auto-scaling parameters reduces the difference between the target utilisation interval and the actual values-we define such difference as Auto-scaling Demand Index. We also present a set of lessons from this study to help cloud providers build recommender systems for auto-scaling operations.