-
作者：Conforti, Michele; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; University of Padua
摘要：We explore one method for finding the convex hull of certain mixed integer sets. The approach is to break up the original set into a small number of subsets, find a compact polyhedral description of the convex hull of each subset, and then take the convex hull of the union of these polyhedra. The resulting extended formulation is then compact, its projection is the convex hull of the original set, and optimization over the mixed integer set is reduced to solving a linear program over the exten...
-
作者：Sun, Defeng; Sun, Jie; Zhang, Liwei
作者单位：National University of Singapore; National University of Singapore; Dalian University of Technology
摘要：We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and t...
-
作者：Pang, Jong-Shi; Stewart, David E.
作者单位：Rensselaer Polytechnic Institute; Rensselaer Polytechnic Institute; University of Iowa
摘要：This paper introduces and studies the class of differential variational inequalities (DVIs) in a finite-dimensional Euclidean space. The DVI provides a powerful modeling paradigm for many applied problems in which dynamics, inequalities, and discontinuities are present; examples of such problems include constrained time-dependent physical systems with unilateral constraints, differential Nash games, and hybrid engineering systems with variable structures. The DVI unifies several mathematical p...
-
作者：Kalantari, B.; Lari, I.; Ricca, F.; Simeone, B.
作者单位：Sapienza University Rome; Rutgers University System; Rutgers University New Brunswick
摘要：Given an n x m nonnegative matrix A = (a(ij)) and positive integral vectors r is an element of R-n and c is an element of R-m having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n x m matrix z = (z(ij)) having the same zero pattern as A, the sum of whose entries is a given number h, its row and ...
-
作者：Takazawa, Kenjiro
作者单位：University of Tokyo; Kyoto University
摘要：An even factor in a digraph, introduced by Cunningham and Geelen (Vertex-disjoint dipaths and even dicircuits. manuscript, 2001), is a collection of vertex-disjoint dipaths and even dicycles, which generalizes a path-matching of Cunningham and Geelen (Combinatorica 17, 315-337, 1997). In a restricted class of digraphs, called odd-cycle-symmetric, Pap (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3509, pp. 66-80, Springer, Heidelberg, 2005) presented a ...
-
作者：Uchoa, Eduardo; Fukasawa, Ricardo; Lysgaard, Jens; Pessoa, Artur; De Aragao, Marcus Poggi; Andrade, Diogo
作者单位：Universidade Federal Fluminense; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Rutgers University System; Rutgers University New Brunswick
摘要：This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms: powerful new cuts expressed ove...
-
作者：Davis, Timothy A.; Hager, WilliamW.
作者单位：State University System of Florida; University of Florida; State University System of Florida; University of Florida
摘要：We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilev...
-
作者：Glover, Fred; Sherali, Hanif D.
作者单位：University of Colorado System; University of Colorado Boulder; Virginia Polytechnic Institute & State University
摘要：We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0-1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and -1. We pr...
-
作者：Bonami, Pierre; Cornuejols, Gerard; Dash, Sanjeeb; Fischetti, Matteo; Lodi, Andrea
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA; Aix-Marseille Universite; University of Padua; University of Bologna
摘要：Recent experiments by Fischetti and Lodi show that the first Chvatal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvatal closure by modeling the Chvatal-Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since ...
-
作者：Briant, O.; Lemarechal, C.; Meurdesoif, Ph.; Michel, S.; Perrot, N.; Vanderbeck, F.
作者单位：Inria; Universite de Bordeaux
摘要：When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle m...
