-
作者：Berger, Andre; Bonifaci, Vincenzo; Grandoni, Fabrizio; Schafer, Guido
作者单位：Sapienza University Rome; Maastricht University; University of L'Aquila; University of Rome Tor Vergata; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam
摘要：Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to ...
-
作者：Karamanov, Miroslav; Cornuejols, Gerard
作者单位：Carnegie Mellon University
摘要：This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relax...
-
作者：Ahmed, Shabbir; Atamtuerk, Alper
作者单位：University of California System; University of California Berkeley; University System of Georgia; Georgia Institute of Technology
摘要：Given a finite ground set N and a value vector a is an element of R-N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S) = f(Sigma(i is an element of S)a(i)), S subset of N, where f is a strictly concave, increasing, differentiable function. This utility function appears frequently in combinatorial optimization problems when modeling risk aversion and decreasing marginal preferences, for instance, in risk-averse capital budgeting und...
-
作者：Avelino, Catarina P.; Moguerza, Javier M.; Olivares, Alberto; Prieto, Francisco J.
作者单位：University of Tras-os-Montes & Alto Douro; Universidad Rey Juan Carlos; Universidad Carlos III de Madrid
摘要：The aim of this paper is the study of different approaches to combine and scale, in an efficient manner, descent information for the solution of unconstrained optimization problems. We consider the situation in which different directions are available in a given iteration, and we wish to analyze how to combine these directions in order to provide a method more efficient and robust than the standard Newton approach. In particular, we will focus on the scaling process that should be carried out ...
-
作者：Bernauer, Martin K.; Griesse, Roland
作者单位：Technische Universitat Chemnitz
摘要：Unconstrained convex quadratic optimization problems subject to parameter perturbations are considered. A robustification approach is proposed and analyzed which reduces the sensitivity of the optimal function value with respect to the parameter. Since reducing the sensitivity and maintaining a small objective value are competing goals, strategies for balancing these two objectives are discussed. Numerical examples illustrate the approach.
-
作者：Ai, Wenbao; Huang, Yongwei; Zhang, Shuzhong
作者单位：Beijing University of Posts & Telecommunications; Chinese University of Hong Kong
摘要：In this paper, we present several new rank-one decomposition theorems for Hermitian positive semidefinite matrices, which generalize our previous results in Huang and Zhang (Math Oper Res 32(3):758-768, 2007), Ai and Zhang (SIAM J Optim 19(4):1735-1756, 2009). The new matrix rank-one decomposition theorems appear to have wide applications in theory as well as in practice. On the theoretical side, for example, we show how to further extend some of the classical results including a lemma due to ...
-
作者：Zhao, Wenhui; Posner, Marc E.
作者单位：Washington University (WUSTL); University System of Ohio; Ohio State University
摘要：The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant.
-
作者：Ma, Shiqian; Goldfarb, Donald; Chen, Lifeng
作者单位：Columbia University
摘要：The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving th...
-
作者：Fukasawa, Ricardo; Goycoolea, Marcos
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
摘要：During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309-326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (...
