-
作者：Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S.; Kaibel, Volker
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidad Catolica de Chile; Otto von Guericke University
摘要：In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations w...
-
作者：Venel, Xavier
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Humanities & Social Sciences (INSHS); heSam Universite; Universite Pantheon-Sorbonne
摘要：We are interested in the convergence of the value of n-stage games as n goes to infinity and the existence of the uniform value in stochastic games with a general set of states and finite sets of actions where the transition is commutative. This means that playing an action profile a(1) followed by an action profile a(2), leads to the same distribution on states as playing first the action profile a(2) and then a(1). For example, absorbing games can be reformulated as commutative stochastic ga...
-
作者：Boxma, Onno; Perry, David; Zacks, Shelley
作者单位：Eindhoven University of Technology; Eindhoven University of Technology; University of Haifa; State University of New York (SUNY) System; Binghamton University, SUNY
摘要：We consider a stochastic fluid EOQ-type model with demand rates operating in a two-state random environment. This environment alternates between exponentially distributed periods of high demand and generally distributed periods of low demand. The inventory level starts at some level q, and decreases linearly at rate, beta(H) during the periods of high demand, and at rate, beta(L) < beta(H) at periods of low demand. Refilling of the inventory level to level q is required when the first of two e...
-
作者：Conforti, Michele; Cornuejols, Gerard; Daniilidis, Aris; Lemarechal, Claude; Malick, Jerome
作者单位：University of Padua; Carnegie Mellon University; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS)
摘要：We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (CGF) and we develop a formal theory for them, largely based on convex analysis. They are...
-
作者：Drusvyatskiy, Dmitriy; Ioffe, Alexander D.; Lewis, Adrian S.
作者单位：University of Washington; University of Washington Seattle; University of Waterloo; Technion Israel Institute of Technology; Cornell University
摘要：Using a geometric argument, we show that under a reasonable continuity condition, the Clarke subdifferential of a semi-algebraic (or more generally stratifiable) directionally Lipschitzian function admits a simple form: The normal cone to the domain and limits of gradients generate the entire Clarke subdifferential. The characterization formula we obtain unifies various apparently disparate results that have appeared in the literature. Our techniques also yield a simplified proof that closed s...
-
作者：Muthuraman, Kumar; Seshadri, Sridhar; Wu, Qi
作者单位：University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; Indian School of Business (ISB); University System of Ohio; Case Western Reserve University
摘要：This article analyzes a continuous time back-ordered inventory system with stochastic demand and stochastic delivery lags for placed orders. This problem in general has an infinite dimensional state space and is hence intractable. We first obtain the set of minimal conditions for reducing such a system's state space to one dimension and show how this reduction is done. Next, by modeling demand as a diffusion process, we reformulate the inventory control problem as an impulse control problem. W...
-
作者：Marechal, Pierre; Ye, Jane J.; Zhou, Julie
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; University of Victoria
摘要：In this paper, we consider the problem of optimal design of experiments. A two-step inference strategy is proposed. The first step consists in minimizing the condition number of the so-called information matrix. This step can be turned into a semidefinite programming problem. The second step is more classical, and it entails the minimization of a convex integral functional under linear constraints. This step is formulated in some infinite-dimensional space and is solved by means of a dual appr...
-
作者：Kanzow, Christian; Schwartz, Alexandra
作者单位：University of Wurzburg; Technical University of Darmstadt
摘要：Mathematical programs with equilibrium (or complementarity) constraints, MPECs for short, form a difficult class of optimization problems. The feasible set has a very special structure and violates most of the standard constraint qualifications. Therefore, one typically applies specialized algorithms in order to solve MPECs. One prominent class of specialized algorithms is the relaxation (or regularization) methods. The first relaxation method for MPECs is due to Scholtes [35] [Scholtes S (200...
-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：Technion Israel Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first o...
-
作者：Murota, Kazuo; Yokoi, Yu
作者单位：University of Tokyo
摘要：The stable allocation model is a many-to-many matching model in which each pair's partnership is represented by a nonnegative integer. This paper establishes a link between two different formulations of this model: the choice function model studied thoroughly by Alkan and Gale and the discrete-concave (M-concave) value function model introduced by Eguchi, Fujishige, and Tamura. We show that the choice functions induced from M-concave value functions are endowed with consistency, persistence, a...
