We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset $I$ of the binary variables. We show that by restricting the support of the cut to the same set of variables $I$, … Read more
In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more
Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. … Read more
Stochastic gradient descent method and its variants constitute the core optimization algorithms that achieve good convergence rates for solving machine learning problems. These rates are obtained especially when these algorithms are fine-tuned for the application at hand. Although this tuning process can require large computational costs, recent work has shown that these costs can be … Read more
We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games defined over series-parallel networks. We introduce a quantity y(D) to upper bound the Price of Anarchy (PoA) for delay functions in class D. When D is the class of polynomial functions with highest degree p, our upper bound is 2^{p+1} − … Read more
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. ArticleDownload View … Read more
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
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
Developing solution methods for discrete 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. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a … Read more
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