-
作者：Adamaszek, Anna; Chalermsook, Parinya; Ene, Alina; Wiese, Andreas
作者单位：University of Copenhagen; Aalto University; University of Warwick; Max Planck Society
摘要：We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our m...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Approximation is central to many optimization problems and the supporting theory provides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing finite- and infinite-dimensional constrained minimization problems as instances of extended real-valued lower semicontinuous functions defined on a general metric space. Since the Attouch-Wets distance between such functions quantifies epi-convergence, we are able to obtain e...
-
作者：Li, G.; Mordukhovich, B. S.; Nghia, T. T. A.; Pham, T. S.
作者单位：University of New South Wales Sydney; Wayne State University; Oakland University
摘要：The paper addresses parametric inequality systems described by polynomial functions in finite dimensions, where state-dependent infinite parameter sets are given by finitely many polynomial inequalities and equalities. Such systems can be viewed, in particular, as solution sets to problems of generalized semi-infinite programming with polynomial data. Exploiting the imposed polynomial structure together with powerful tools of variational analysis and semialgebraic geometry, we establish a far-...
-
作者：Xie, Weijun; Ahmed, Shabbir
作者单位：Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
摘要：A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MINLP for...
-
作者：Permenter, Frank; Parrilo, Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We develop a practical semidefinite programming (SDP) facial reduction procedure that utilizes computationally efficient approximations of the positive semidefinite cone. The proposed method simplifies SDPs with no strictly feasible solution (a frequent output of parsers) by solving a sequence of easier optimization problems and could be a useful pre-processing technique for SDP solvers. We demonstrate effectiveness of the method on SDPs arising in practice, and describe our publicly-available...
-
作者：Basu, Amitabh; Hildebrand, Robert; Molinaro, Marco
作者单位：Johns Hopkins University; International Business Machines (IBM); IBM USA; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Yldz and Cornuejols (Math Oper Res 41:1381-1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions a...
-
作者：Borgwardt, S.; De Loera, J. A.; Finhold, E.
作者单位：University of Colorado System; University of Colorado Denver; University of California System; University of California Davis; Fraunhofer Gesellschaft
摘要：We solve a problem in the combinatorics of polyhedra motivated by the network simplex method. We show that the Hirsch conjecture holds for the diameter of the graphs of all network-flow polytopes, in particular the diameter of a network-flow polytope for a network with n nodes and m arcs is never more than m + n - 1. A key step to prove this is to show the same result for classical transportation polytopes.
-
作者：Junger, Michael; Vanderbeck, Francois
-
作者：Fischetti, Matteo; Ljubic, Ivana; Monaci, Michele; Sinnl, Markus
作者单位：University of Padua; ESSEC Business School; University of Bologna; University of Vienna
摘要：We address a generic mixed-integer bilevel linear program (MIBLP), i.e., a bilevel optimization problem where all objective functions and constraints are linear, and some/all variables are required to take integer values. We first propose necessary modifications needed to turn a standard branch-and-bound MILP solver into an exact and finitely-convergent MIBLP solver, also addressing MIBLP unboundedness and infeasibility. As in other approaches from the literature, our scheme is finitely-conver...
-
作者：Lim, Cong Han; Linderoth, Jeff; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MI...
