-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
-
作者：Bodur, Merve; Luedtke, James R.
作者单位：University of Toronto; University of Wisconsin System; University of Wisconsin Madison
摘要：Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn et al. (M...
-
作者：Harks, Tobias; Timmermans, Veerle
作者单位：RWTH Aachen University
摘要：We study the equilibrium computation problem for two classical resource allocation games: atomic splittable congestion games and multimarket Cournot oligopolies. For atomic splittable congestion games with singleton strategies and player-specific affine cost functions, we devise the first polynomial time algorithm computing a pure Nash equilibrium. Our algorithm is combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute an equilibrium for an associated ...
-
作者：Gokmen, Y. Gorkem; Yildirim, E. Alper
作者单位：Izmir Ekonomi Universitesi; University of Edinburgh
摘要：The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose ...
-
作者：DeCorte, Evan; Filho, Fernando Mario de Oliveira; Vallentin, Frank
作者单位：McGill University; Delft University of Technology; University of Cologne
摘要：We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.
-
作者：Coniglio, Stefano; Furini, Fabio; Ljubic, Ivana
作者单位：University of Southampton; University of Bergamo; Sapienza University Rome; ESSEC Business School
摘要：We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of met...
-
作者：Malaguti, Enrico; Monaci, Michele; Pruente, Jonas
作者单位：University of Bologna; Dortmund University of Technology
摘要：We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomia...
-
作者：Bolte, Jerome; Pauwels, Edouard
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：Counterexamples to some old-standing optimization problems in the smooth convex coercive setting are provided. We show that block-coordinate, steepest descent with exact search or Bregman descent methods do not generally converge. Other failures of various desirable features are established: directional convergence of Cauchy's gradient curves, convergence of Newton's flow, finite length of Tikhonov path, convergence of central paths, or smooth Kurdyka-Lojasiewicz inequality. All examples are p...
-
作者：Castro, Margarita P.; Cire, Andre A.; Beck, J. Christopher
作者单位：Pontificia Universidad Catolica de Chile; University of Toronto; University Toronto Scarborough; University of Toronto
摘要：Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a wide range of binary optimization problems and show its applicability for second-order conic inequalities. We identify conditions for which o...
-
作者：Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen
作者单位：Carnegie Mellon University; Northwestern University; Institute for Basic Science - Korea (IBS)
摘要：A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities assoc...
