-
作者：Krislock, Nathan; Malick, Jerome; Roupin, Frederic
作者单位：University of British Columbia; Northern Illinois University; Centre National de la Recherche Scientifique (CNRS); Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness ...
-
作者：Lange, Kenneth; Zhou, Hua
作者单位：University of California System; University of California Los Angeles; University of California System; University of California Los Angeles; University of California System; University of California Los Angeles; North Carolina State University
摘要：This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate t...
-
作者：Michini, Carla; Sassano, Antonio
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Sapienza University Rome
摘要：The edge formulation of the stable set problem is defined by two-variable constraints, one for each edge of a graph , expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorith...
-
作者：Flores-Bazan, Fabian; Carcamo, Gabriel
作者单位：Universidad de Concepcion; Universidad de Concepcion
摘要：We first establish a relaxed version of Dines theorem associated to quadratic minimization problems with finitely many linear equality and a single (nonconvex) quadratic inequality constraints. The case of unbounded optimal valued is also discussed. Then, we characterize geometrically the strong duality, and some relationships with the conditions employed in Finsler theorem are established. Furthermore, necessary and sufficient optimality conditions with or without the Slater assumption are de...
-
作者：Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick
-
作者：Izmailov, Alexey F.
摘要：This note presents an implicit function theorem for generalized equations, simultaneously generalizing Robinson's implicit function theorem for strongly regular generalized equations and Clarke's implicit function theorem for equations with Lipschitz-continuous mappings.
-
作者：Gade, Dinakar; Kuecuekyavuz, Simge; Sen, Suvrajeet
作者单位：University System of Ohio; Ohio State University
摘要：We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the -shaped or Benders' methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illu...
-
作者：Ames, Brendan P. W.
作者单位：California Institute of Technology
摘要：Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest -disjoint-clique problem, whose goal is to identify the collection of disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest cliques of a given graph from the optimal sol...
-
作者：Vera, Jorge R.
作者单位：Pontificia Universidad Catolica de Chile
摘要：The effect of data perturbation and uncertainty has always been an important consideration in Optimization. It is important to know whether a given problem is very sensible to perturbations on the data or, on the contrary, is more robust. Problem geometry does have an impact on the sensitivity of the problem and in this paper we analyze this connection by developing bounds to the change in the optimal value of a conic linear problem in terms of some geometric measures related to the radius of ...
-
作者：Wang, Xiumei; Song, Xiaoxin; Yuan, Jinjiang
作者单位：Zhengzhou University; Henan University
摘要：A k-matching cover of a graph is a union of matchings of which covers . The matching cover number of , denoted by , is the minimum number such that has a -matching cover. A matching cover of is optimal if it consists of matchings of . In this paper, we present an algorithm for finding an optimal matching cover of a graph on vertices in time (if use a faster maximum matching algorithm, the time complexity can be reduced to , where ), and give an upper bound on matching cover number of graphs. I...
