-
作者：Kocyigit, Cagil; Rujeerapaiboon, Napat; Kuhn, Daniel
作者单位：University of Luxembourg; National University of Singapore; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pricing problem as a zero-sum game between the seller, who chooses a selling mechanism, and a fictitious adversary or 'nature', who chooses the buyer's values from within the uncertainty set. Using duality techniques rooted in robust optimizati...
-
作者：Zhang, Shixuan; Sun, Xu Andy
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based o...
-
作者：Fujishige, Satoru; Tardella, Fabio
作者单位：Kyoto University; University of Florence
摘要：We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M-(sic)-convex and L-/L-(sic)-convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS*- convex and UJ-convex fu...
-
作者：Barmann, Andreas; Schneider, Oskar
作者单位：University of Erlangen Nuremberg; Fraunhofer Gesellschaft
摘要：In the present work, we consider Zuckerberg's method for geometric convex-hull proofs introduced in Zuckerberg (Oper Res Lett 44(5):625-629, 2016). It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. We suspect that this is partly due to the rather heavy algebraic framework its original statement entails. This is why we present a much more lightweight and access...
-
作者：Gupta, Swati; Khodabakhsh, Ali; Mortagy, Hassan; Nikolova, Evdokia
作者单位：University System of Georgia; Georgia Institute of Technology; University of Texas System; University of Texas Austin
摘要：The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the...
-
作者：Ho-Nguyen, Nam; Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen
作者单位：University of Sydney; Carnegie Mellon University; Northwestern University; Institute for Basic Science - Korea (IBS)
摘要：We consider exact deterministic mixed-integer programming (MIP) reformulations of distributionally robust chance-constrained programs (DR-CCP) with random right-hand sides over Wasserstein ambiguity sets. The existing MIP formulations are known to have weak continuous relaxation bounds, and, consequently, for hard instances with small radius, or with large problem sizes, the branch-and-bound based solution processes suffer from large optimality gaps even after hours of computation time. This s...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Huynh, Tony; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Monash University; Institute for Basic Science - Korea (IBS)
-
作者：Mueller, Benjamin; Munoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe
作者单位：Zuse Institute Berlin; Universidad de O'Higgins; Universite de Montreal; Polytechnique Montreal
摘要：Themost important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In th...
-
作者：Shi, Bin; Du, Simon S.; Jordan, Michael, I; Su, Weijie J.
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; University of Washington; University of Washington Seattle; University of California System; University of California Berkeley; University of Pennsylvania
摘要：Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODES do not distinguish between two fundamentally different algorithms-Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method-we study an alternative limiting process that yields high-resolution ODEs. We show that these ODES permit a general Lyapunov function framework for the ana...
-
作者：Esteban-Perez, Adrian; Morales, Juan M.
作者单位：Universidad de Malaga
摘要：We consider stochastic programs conditional on some covariate information, where the only knowledge of the possible relationship between the uncertain parameters and the covariates is reduced to a finite data sample of their joint distribution. By exploiting the close link between the notion of trimmings of a probability measure and the partial mass transportation problem, we construct a data-driven Distributionally Robust Optimization (DRO) framework to hedge the decision against the intrinsi...
