-
作者：Soma, Tasuku; Yoshida, Yuichi
作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a nonnegative monotone submodular function f : Zn +. R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Giv...
-
作者：Bertsimas, Dimitris; Gupta, Vishal; Kallus, Nathan
作者单位：Massachusetts Institute of Technology (MIT); University of Southern California; Cornell University; Cornell University
摘要：Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to...
-
作者：Bodur, Merve; Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco; Pokutta, Sebastian
作者单位：University of Toronto; University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first ma...
-
作者：Ahmed, Shabbir; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology; Virginia Polytechnic Institute & State University
摘要：Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulat...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Hildebrand, Robert
作者单位：International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University
摘要：We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call unimodular extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature...
-
作者：Carrizosa, Emilio; Guerrero, Vanesa; Morales, Dolores Romero
作者单位：University of Sevilla; Copenhagen Business School
摘要：In this paper we address the problem of visualizing in a bounded region a set of individuals, which has attached a dissimilarity measure and a statistical value, as convex objects. This problem, which extends the standard Multidimensional Scaling Analysis, is written as a global optimization problem whose objective is the difference of two convex functions (DC). Suitable DC decompositions allow us to use the Difference of Convex Algorithm (DCA) in a very efficient way. Our algorithmic approach...
-
作者：Maehara, Takanori; Marumo, Naoki; Murota, Kazuo
作者单位：Shizuoka University; RIKEN; University of Tokyo; Tokyo Metropolitan University
摘要：Discrete DC programming with convex extensible functions is studied. A natural approach for this problem is a continuous relaxation that extends the problem to a continuous domain and applies the algorithm in continuous DC programming. By employing a special form of continuous relaxation, which is named lin-vex extension, the produced optimal solution of the extended continuous relaxation coincides with the solution of the original discrete problem. The proposed method is demonstrated for the ...
-
作者：Sun, Jie; Liao, Li-Zhi; Rodrigues, Brian
作者单位：Curtin University; Curtin University; National University of Singapore; Hong Kong Baptist University; Singapore Management University
摘要：A new scheme to cope with two-stage stochastic optimization problems uses a risk measure as the objective function of the recourse action, where the risk measure is defined as the worst-case expected values over a set of constrained distributions. This paper develops an approach to deal with the case where both the first and second stage objective functions are convex linear-quadratic. It is shown that under a standard set of regularity assumptions, this two-stage quadratic stochastic optimiza...
-
作者：Averkov, Gennadiy; Kaibel, Volker; Weltge, Stefan
作者单位：Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known pr...
-
作者：Cornuejols, Gerard; Lee, Dabeen
作者单位：Carnegie Mellon University
摘要：In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0, 1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvatal rank is at most 3; and when it has tree width 2, the Chvatal rank is at most 4. We also giv...
