On the Complexity of Separation From the Knapsack Polytope

We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also give a number of special cases where the separation problem can be solved in polynomial time. Article Download … Read more

Distributionally Robust Optimization with Expected Constraints via Optimal Transport

We consider a stochastic program with expected value constraints. We analyze this problem in a general context via Distributionally Robust Optimization (DRO) approach using 1 or 2-Wasserstein metrics where the ambiguity set depends on the decision. We show that this approach can be reformulated as a finite-dimensional optimization problem, and, in some cases, this can … Read more

On the Fairness of Aggregator’s Incentives in Residential Demand Response

The main motivation of this work is to provide an optimization-based tool for an aggregator involved in residential demand response (DR) programs. The proposed tool comply with the following requirements, which are widely accepted by the residential DR literature: (i) the aggregated consumption should be optimized under a particular utility’s target, such as the minimization … Read more

Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem

Developing solution methods for mixed-integer bilevel problems is known to be a challenging task – even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty due to some kind of bounded rationality. We study mixed-integer min-max problems with a follower who faces uncertainties regarding the … Read more

Model-Based Derivative-Free Methods for Convex-Constrained Optimization

We present a model-based derivative-free method for optimization subject to general convex constraints, which we assume are unrelaxable and accessed only through a projection operator that is cheap to evaluate. We prove global convergence and a worst-case complexity of $O(\epsilon^{-2})$ iterations and objective evaluations for nonconvex functions, matching results for the unconstrained case. We introduce … Read more

Mixed-Integer Optimization with Constraint Learning

We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We propose an end-to-end pipeline for data-driven decision making in which constraints and objectives are directly learned from data using machine learning, and the trained models are embedded in an optimization formulation. We exploit the mixed-integer optimization-representability of many machine learning methods, including … Read more

A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems

In this paper, we study a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently … Read more

Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems

We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop … Read more

A Robust Optimization Method with Successive Linear Programming for Intensity Modulated Radiation Therapy

Intensity modulated radiation therapy (IMRT) is one of radiation therapies for cancers, and it is considered to be effective for complicated shapes of tumors, since dose distributions from each irradiation can be modulated arbitrary. Fluence map optimization (FMO), which optimizes beam intensities with given beam angles, is often formulated as an optimization problem with dose … Read more

Simple odd beta-cycle inequalities for binary polynomial optimization

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle … Read more