-
作者：Basu, Amitabh; Ryan, Christopher Thomas; Sankaranarayanan, Sriram
作者单位：Johns Hopkins University; University of Chicago; Universite de Montreal; Polytechnique Montreal
摘要：We study the representability of sets by extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these three paradigms. We then prove that the feasible region of bilevel problems with integer variables exclus...
-
作者：Yu, Jing; Anitescu, Mihai
作者单位：University of Chicago; United States Department of Energy (DOE); Argonne National Laboratory
摘要：We present a numerical method for approximating the solution of convex integer programs stemming from optimal experimental design. The statistical setup consists of a Bayesian framework for linear inverse problems for which the direct relationship is described by a discretized integral equation. Specifically, we aim to find the optimal sensor placement from a set of candidate locations where data are collected with measurement error. The convex objective function is a measure of the uncertaint...
-
作者：Zhan, Yang; Dang, Chuangyin
作者单位：Nanjing University; City University of Hong Kong
摘要：In the general equilibrium with incomplete asset markets (GEI) model, the excess demand functions are typically not continuous at the prices for which the assets have redundant returns. The reason is that, at these prices, the return matrix drops rank and households' budget sets collapse suddenly. This discontinuity results in a serious problem for the existence and computation of general equilibrium. In this paper, we show that this problem can be resolved with a new return matrix, which has ...
-
作者：Zeile, Clemens; Robuschi, Nicolo; Sager, Sebastian
作者单位：Otto von Guericke University; Polytechnic University of Milan
摘要：Tailored Mixed-Integer Optimal Control policies for real-world applications usually have to avoid very short successive changes of the active integer control. Minimum dwell time (MDT) constraints express this requirement and can be included into the combinatorial integral approximation decomposition, which solves mixed-integer optimal control problems (MIOCPs) to epsilon-optimality by solving one continuous nonlinear program and one mixed-integer linear program (MILP). Within this work, we ana...
-
作者：Kocvara, Michal
作者单位：University of Birmingham; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
摘要：Decomposition of large matrix inequalities for matrices with chordal sparsity graph has been recently used by Kojima et al. (Math Program 129(1):33-68, 2011) to reduce problem size of large scale semidefinite optimization (SDO) problems and thus increase efficiency of standard SDO software. A by-product of such a decomposition is the introduction of new dense small-size matrix variables. We will show that for arrow type matrices satisfying suitable assumptions, the additional matrix variables ...
-
作者：Chervet, Patrick; Grappe, Roland; Robert, Louis-Hadrien
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Geneva
摘要：Box-totally dual integral (box-TDI) polyhedra are polyhedra described by systems which yield strong min-max relations. We characterize them in several ways, involving the notions of principal box-integer polyhedra and equimodular matrices. A polyhedron is box-integer if its intersection with any integer box {l <= x <= u} is integer. We define principally box-integer polyhedra to be the polyhedra P such that kP is box-integer whenever kP is integer. A rational r x n matrix is equimodular if it ...
-
作者：Dinh The Luc; Volle, Michel
作者单位：Ton Duc Thang University; Ton Duc Thang University; Avignon Universite
摘要：We establish necessary and sufficient conditions for strong duality of extended monotropic optimization problems with possibly infinite sum of separable functions. The results are applied to a minimization problem of the infinite sum of proper convex functions. We consider a truncation method for duality and obtain the zero duality gap by using only dual variable of finite support. An application to minimum cost flow problems in infinite networks is also discussed.
-
作者：Beer, G.; Canovas, M. J.; Lopez, M. A.; Parra, J.
作者单位：California State University System; California State University Los Angeles; Universidad Miguel Hernandez de Elche; Universitat d'Alacant; Federation University Australia
摘要：This paper analyzes the Lipschitz behavior of the feasible set mapping associated with linear and convex inequality systems in R-n. To start with, we deal with the parameter space of linear (finite/semi-infinite) systems identified with the corresponding sets of coefficient vectors, which are assumed to be closed subsets of Rn+1. In this framework the size of perturbations is measured by means of the (extended) Hausdorff distance. A direct antecedent, extensively studied in the literature, com...
-
作者：Letchford, Adam N.; Vu, Anh N.
作者单位：Lancaster University
摘要：We present a new tool for generating cutting planes for NP\-hard combinatorial optimisation problems. It is based on the concept of gadgets-small subproblems that are glued together to form hard problems-which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families of strong (and sometimes facet-defining) cutting planes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the...
-
作者：Zhang, Richard Y.; Lavaei, Javad
作者单位：University of California System; University of California Berkeley; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Clique tree conversion solves large-scale semidefinite programs by splitting an nxn matrix variable into up to n smaller matrix variables, each representing a principal submatrix of up to omega x omega. Its fundamental weakness is the need to introduce overlap constraints that enforce agreement between different matrix variables, because these can result in dense coupling. In this paper, we show that by dualizing the clique tree conversion, the coupling due to the overlap constraints is guaran...
