-
作者：Granot, Frieda; McCormick, S. Thomas; Queyranne, Maurice; Tardella, Fabio
作者单位：Sapienza University Rome
摘要：We consider the minimum s, t-cut problem in a network with parametrized arc capacities. Following the seminal work of Gallo et al. (SIAM J. Comput. 18(1):30-55, 1989), classes of this parametric problem have been shown to enjoy the nice Structural Property that minimum cuts are nested, and the nice Algorithmic Property that all minimum cuts can be computed in the same asymptotic time as a single minimum cut by using a clever Flow Update step to move from one value of the parameter to the next....
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：A set is called semidefinite representable or semidefinite programming (SDP) representable if it equals the projection of a higher dimensional set which is defined by some Linear Matrix Inequality (LMI). This paper discusses the semidefinite representability conditions for convex sets of the form S-D(f) = {x is an element of D : f (x) >= 0}. Here, D = {x is an element of R-n : g(1)(x) >= 0, ..., g(m)(x) >= 0} is a convex domain defined by some nice concave polynomials g(i)(x) (they satisfy cer...
-
作者：Andreani, Roberto; Haeser, Gabriel; Laura Schuverdt, Maria; Silva, Paulo J. S.
作者单位：Universidade de Sao Paulo; Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of La Plata; Universidade Federal de Sao Paulo (UNIFESP); Universidade Estadual de Campinas
摘要：In this work we introduce a relaxed version of the constant positive linear dependence constraint qualification (CPLD) that we call RCPLD. This development is inspired by a recent generalization of the constant rank constraint qualification by Minchenko and Stakhovski that was called RCRCQ. We show that RCPLD is enough to ensure the convergence of an augmented Lagrangian algorithm and that it asserts the validity of an error bound. We also provide proofs and counter-examples that show the rela...
-
作者：Chubanov, Sergei
作者单位：Universitat Siegen
摘要：This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax = b, 0 a parts per thousand currency sign x a parts per thousand currency sign 1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.
-
作者：Takazawa, Kenjiro
作者单位：Kyoto University
摘要：An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cun...
-
作者：Yamashita, Hiroshi; Yabe, Hiroshi; Harada, Kouhei
作者单位：Tokyo University of Science
摘要：This paper is concerned with a primal-dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal-dual barrier function, a new primal-dual me...
-
作者：Hu, Jian; Homem-de-Mello, Tito; Mehrotra, Sanjay
作者单位：Northwestern University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of -dominance, which generalizes some notions of multi-variate do...
-
作者：Aravkin, Aleksandr; Friedlander, Michael P.; Herrmann, Felix J.; van Leeuwen, Tristan
作者单位：University of British Columbia; University of British Columbia
摘要：We consider a class of inverse problems in which the forward model is the solution operator to linear ODEs or PDEs. This class admits several dimensionality-reduction techniques based on data averaging or sampling, which are especially useful for large-scale problems. We survey these approaches and their connection to stochastic optimization. The data-averaging approach is only viable, however, for a least-squares misfit, which is sensitive to outliers in the data and artifacts unexplained by ...
-
作者：Dash, Sanjeeb; Dey, Santanu S.; Guenluek, Oktay
作者单位：International Business Machines (IBM); IBM USA; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical So...
-
作者：Kobayashi, Yusuke; Murota, Kazuo; Weismantel, Robert
作者单位：University of Tokyo; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：A function f is said to be cone superadditive if there exists a partition of R (n) into a family of polyhedral convex cones such that f(z + x) + f(z + y) a parts per thousand currency sign f(z) + f(z + x + y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper show...
