-
作者：Locatelli, Marco
作者单位：University of Parma
摘要：The Lovasz and Lovasz-Schrijver bounds are well known upper bounds for the clique number of a graph, based on the solution of semidefinite programming problems. Both bounds can be seen as obtained through a relaxation of a completely positive formulation of the maximum clique problem. In this paper we propose to improve these bounds by adding inequalities based on independent sets, which may be non-valid, in the sense that they may be violated by optimal solutions of the completely positive fo...
-
作者：Bertsimas, Dimitris; Bidkhori, Hoda
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider two-stage adjustable robust linear optimization problems with uncertain right hand side b belonging to a convex and compact uncertainty set u. We provide an a priori approximation bound on the ratio of the optimal affine (in b) solution to the optimal adjustable solution that depends on two fundamental geometric properties of u: (a) the symmetry and (b) the simplex dilation factor of the uncertainty set u and provides deeper insight on the power of affine policies for this class of...
-
作者：Cucker, Felipe; Pena, Javier; Roshchina, Vera
作者单位：City University of Hong Kong; Carnegie Mellon University; Federation University Australia
摘要：We describe and analyze an interior-point method to decide feasibility problems of second-order conic systems. A main feature of our algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.
-
作者：Boland, N. L.; Eberhard, A. C.
作者单位：University of Newcastle; Royal Melbourne Institute of Technology (RMIT)
摘要：We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a fixed, large value and still obtain strong duality for pure integer programs.
-
作者：Lee, James R.; Mendel, Manor; Moharrami, Mohammad
作者单位：University of Washington; University of Washington Seattle; Open University Israel
摘要：The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal epsilon > 0, if the node cut conditions are satisfied, then ...
-
作者：Bomze, Immanuel M.; Overton, Michael L.
作者单位：University of Vienna; New York University
摘要：We study the Celis-Dennis-Tapia (CDT) problem: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that occurs when the Hessian of the Lagrangian is indefinite at all Karush-Kuhn-Tucker points. We prove new sufficient and necessary conditions both for local a...
-
作者：Bot, Radu Ioan; Csetnek, Erno Robert; Heinrich, Andre; Hendrich, Christopher
作者单位：University of Vienna; Technische Universitat Chemnitz
摘要：We present two modified versions of the primal-dual splitting algorithm relying on forward-backward splitting proposed in V (Adv Comput Math 38(3):667-681, 2013) for solving monotone inclusion problems. Under strong monotonicity assumptions for some of the operators involved we obtain for the sequences of iterates that approach the solution orders of convergence of and , for , respectively. The investigated primal-dual algorithms are fully decomposable, in the sense that the operators are proc...
-
作者：Chubanov, Sergei
作者单位：Universitat Siegen
摘要：We propose a polynomial algorithm for linear feasibility problems. The algorithm represents a linear problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure which either finds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the homogeneous system so that its feasible solutions in the unit cube get closer to the vector of all ones. In a polynomial number of calls to the proced...
-
作者：Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.
作者单位：Lancaster University
摘要：The reformulation-linearization technique, due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. Computational experiments, conduct...
-
作者：Bertsimas, Dimitris; Gupta, Vishal; Paschalidis, Ioannis Ch.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Boston University
摘要：Equilibrium modeling is common in a variety of fields such as game theory and transportation science. The inputs for these models, however, are often difficult to estimate, while their outputs, i.e., the equilibria they are meant to describe, are often directly observable. By combining ideas from inverse optimization with the theory of variational inequalities, we develop an efficient, data-driven technique for estimating the parameters of these models from observed equilibria. We use this tec...
