-
作者：Zanette, Arrigo; Fischetti, Matteo; Balas, Egon
作者单位：University of Padua; Carnegie Mellon University
摘要：We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for ILP problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact soluti...
-
作者：Ames, Brendan P. W.; Vavasis, Stephen A.
作者单位：University of Waterloo
摘要：We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special case that the input graph has a planted clique or biclique (i.e., a singl...
-
作者：Ostrowski, James; Linderoth, Jeff; Rossi, Fabrizio; Smriglio, Stefano
作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University; University of L'Aquila
摘要：We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while stil...
-
作者：Kuhn, Daniel; Wiesemann, Wolfram; Georghiou, Angelos
作者单位：Imperial College London
摘要：Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an effi...
-
作者：Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew
作者单位：Toyota Technological Institute - Chicago; Hebrew University of Jerusalem; Alphabet Inc.; Google Incorporated
摘要：We describe and analyze a simple and effective stochastic sub-gradient descent algorithm for solving the optimization problem cast by Support Vector Machines (SVM). We prove that the number of iterations required to obtain a solution of accuracy epsilon is (O) over tilde (1/epsilon), where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs require Omega(1/epsilon(2)) iterations. As in previously devised SVM solve...
-
作者：Kim, Sunyoung; Kojima, Masakazu; Mevissen, Martin; Yamashita, Makoto
作者单位：Ewha Womans University; Institute of Science Tokyo; Tokyo Institute of Technology
摘要：A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint...
-
作者：Addi, Khalid; Brogliato, B.; Goeleven, D.
作者单位：University of La Reunion; Inria
摘要：The main object of this paper is to present a general mathematical theory applicable to the study of a large class of linear variational inequalities arising in electronics. Our approach uses recession tools so as to define a new class of problems that we call semi-complementarity problems. Then we show that the study of semi-complementarity problems can be used to prove new qualitative results applicable to the study of linear variational inequalities of the second kind.
-
作者：Alfakih, A. Y.
作者单位：University of Windsor
摘要：A bar framework G(p) in r-dimensional Euclidean space is a graph G on the vertices 1,2,...,n, where each vertex i is located at point p(i) in R-r. Given a framework G(p) in R-r, a problem of great interest is that of determining whether or not there exists another framework G(q), not obtained from G(p) by a rigid motion, such that parallel to q(i) - q(j)parallel to(2) = parallel to p(i) - p(j)parallel to(2) for each edge (i, j) of G. This problem is known as either the global rigidity problem ...
-
作者：Fabian, Csaba I.; Mitra, Gautam; Roman, Diana
作者单位：Brunel University; Eotvos Lorand University
摘要：Second-order stochastic dominance (SSD) is widely recognised as an important decision criterion in portfolio selection. Unfortunately, stochastic dominance models are known to be very demanding from a computational point of view. In this paper we consider two classes of models which use SSD as a choice criterion. The first, proposed by Dentcheva and RuszczyAski (J Bank Finance 30:433-451, 2006), uses a SSD constraint, which can be expressed as integrated chance constraints (ICCs). The second, ...
-
作者：Gollmer, Ralf; Gotzes, Uwe; Schultz, Ruediger
作者单位：University of Duisburg Essen
摘要：We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed-integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instan...
