-
作者：Lewis, Mark E.; Paul, Anand
作者单位：Cornell University; State University System of Florida; University of Florida
摘要：A turnpike integer is the smallest finite horizon for which an optimal infinite horizon decision is the optimal initial decision. An important practical question considered in the literature is how to bound the turnpike integer using only the problem inputs. In this paper, we consider turnpike integers as a function of the discount factor. While a turnpike integer is finite for any fixed discount factor, we show that it approaches infinity in the neighborhood of a specific set of discount rate...
-
作者：Tien-Son Pham
作者单位：Ton Duc Thang University; Ton Duc Thang University
摘要：In this paper we study necessary optimality conditions for the problem of minimizing a polynomial function over a set defined by polynomial inequalities. Assume that the problem is bounded below and has the Mangasarian-Fromovitz property at infinity. We first show that if the problem does not have an optimal solution, then a version at infinity of the Fritz John optimality conditions holds. From this we derive a version at infinity of the Karush-Kuhn-Tucker optimality conditions. As applicatio...
-
作者：Ahmadi, Amir Ali; Hall, Georgina
作者单位：INSEAD Business School
摘要：In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensatze from the late 20th century (e.g., due to Stengle, Putinar, or Schmudgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed fr...
-
作者：Armony, Mor; Atar, Rami; Honnappa, Harsha
作者单位：New York University; Technion Israel Institute of Technology; Purdue University System; Purdue University
摘要：We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows to minimize the sum of customer waiting time and server overtime costs. Because appointments need to be scheduled ahead of time, we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show th...
-
作者：Lasserre, Jean B.; Emin, Youssouf
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Institut Polytechnique de Paris; Ecole Polytechnique
摘要：Given a finite Bard measure mu on R-n and basic semialgebraic sets Omega(i) subset of R-n, i=1, ..., p, we provide a systematic numerical scheme to approximate as closely as desired mu(U-i Omega(i)), when all moments of mu are available (and finite). More precisely, we provide a hierarchy of semidefinite programs whose associated sequence of optimal values is monotone and converges to the desired value from above. The same methodology applied to the complement R-n \ (U-i Omega(i))provides a mo...
-
作者：Ngoc Mai Tran; Yu, Josephine
作者单位：University of Texas System; University of Texas Austin; University of Bonn; University System of Georgia; Georgia Institute of Technology
摘要：In a recent and ongoing work, Baldwin and Klemperer explore a connection between tropical geometry and economics. They give a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the unimodularity theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota in discrete convex analysis. We give a new proof of the unimodularity theorem via the classical unimodularity theorem in integer programm...
-
作者：Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas; Wang, Guanyi
作者单位：Johns Hopkins University; University of Chicago; University System of Georgia; Georgia Institute of Technology
摘要：Jeroslow and Lowe gave an exact geometric characterization of subsets of R-n that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showing that a set is MILP-R if and only if the set can be described as the intersection of finitely many affine Chvatal inequalities in continuous variables (termed AC sets). These inequalities are a modification of a concept introduced by Blair and Jeroslow. Unlike th...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Zambelli, Giacomo
作者单位：Johns Hopkins University; University of Padua; University of London; London School Economics & Political Science
摘要：We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson's finite and infinite group models, and we describe valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the finite group model of prime order, we show that the unique maximizer is an automorphism of the Gomory mixed-integer (GMI) cut for a possibly different finite...
-
作者：Marinacci, Massimo; Montrucchio, Luigi
作者单位：Bocconi University; Bocconi University; Collegio Carlo Alberto; University of Turin
摘要：We establish sufficient conditions that ensure the uniqueness of Tarski-type fixed points of monotone operators. A first set of results relies on order concavity, whereas a second one uses subhomogeneity. A few applications that illustrate our results are presented.
-
作者：Fokkink, Robbert J.; Lidbetter, Thomas; Vegh, Laszlo A.
作者单位：Delft University of Technology; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; University of London; London School Economics & Political Science
摘要：Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of S that finds all the objects with minimal expected cost. This problem is NP-hard, and we give an efficient combinatorial 2-approximation algorithm, generalizing analogous results in scheduling theory...
