-
作者：Baardman, Lennart; Cristian, Rares; Perakis, Georgia; Singhvi, Divya; Lami, Omar Skali; Thayaparan, Leann
作者单位：University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT); New York University
摘要：Data-driven decision-making has garnered growing interest as a result of the increasing availability of data in recent years. With that growth many opportunities and challenges have sprung up in the areas of predictive and prescriptive analytics. Often, optimization can play an important role in tackling these issues. In this paper, we review some recent advances that highlight the difference that optimization can make in data-driven decision-making. We discuss some of our contributions that a...
-
作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form pi(T) x <= pi(0) V pi(T) x >= pi(0) + 1, where pi is an integer vector and pi(0) is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the ...
-
作者：Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean
作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; International Business Machines (IBM); IBM USA; University of London; London Business School
-
作者：Cui, Shisheng; Shanbhag, Uday, V
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：We consider a class of noncooperative hierarchical N-player games where the ith player solves a parametrized stochastic mathematical program with equilibrium constraints (MPEC) with the caveat that the implicit form of the ith player's in MPEC is convex in player strategy, given rival decisions. Few, if any, general purpose schemes exist for computing equilibria, motivating the development of computational schemes in two regimes: (a) Monotone regimes. When player-specific implicit problems are...
-
作者：Faenza, Yuri; Segev, Danny; Zhang, Lingyi
作者单位：Columbia University; Tel Aviv University
摘要：We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W-1 <= ... <= W-T. When item i is inserted at time t, we gain a profit of p(it ); however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the ...
-
作者：Davis, Damek Shea; Guenluek, Oktay; Kaibel, Volker; Nannicini, Giacomo; Yuan, Xa-Xiang
作者单位：Cornell University; Otto von Guericke University; University of Southern California; Chinese Academy of Sciences
-
作者：Na, Sen; Anitescu, Mihai; Kolar, Mladen
作者单位：University of California System; University of California Berkeley; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
摘要：We study nonlinear optimization problems with a stochastic objective and deterministic equality and inequality constraints, which emerge in numerous applications including finance, manufacturing, power systems and, recently, deep neural networks. We propose an active-set stochastic sequential quadratic programming (StoSQP) algorithm that utilizes a differentiable exact augmented Lagrangian as the merit function. The algorithm adaptively selects the penalty parameters of the augmented Lagrangia...
-
作者：Xiao, Han; Fang, Qizhi
作者单位：Ocean University of China
摘要：The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for comp...
-
作者：Selvi, Aras; den Hertog, Dick; Wiesemann, Wolfram
作者单位：Imperial College London; University of Amsterdam
摘要：We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decisi...
-
作者：Yang, Heng; Liang, Ling; Carlone, Luca; Toh, Kim-Chuan
作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT); National University of Singapore; National University of Singapore
摘要：We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone...
