-
作者：He, Qie; Ahmed, Shabbir; Nemhauser, George L.
作者单位：University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology
摘要：The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple e...
-
作者：Huang, Chien-Chung; Kavitha, Telikepalli
作者单位：Chalmers University of Technology; Tata Institute of Fundamental Research (TIFR)
摘要：We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that...
-
作者：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...
-
作者：Netzer, Tim; Sanyal, Raman
作者单位：Leipzig University; Free University of Berlin
摘要：Hyperbolicity cones are convex algebraic cones arising from hyperbolic polynomials. A well-understood subclass of hyperbolicity cones is that of spectrahedral cones and it is conjectured that every hyperbolicity cone is spectrahedral. In this paper we prove a weaker version of this conjecture by showing that every smooth hyperbolicity cone is the linear projection of a spectrahedral cone, that is, a spectrahedral shadow.
-
作者：Cornuejols, Gerard; Wolsey, Laurence; Yildiz, Sercan
作者单位：Carnegie Mellon University; Universite Catholique Louvain
摘要：The concept of cut-generating function has its origin in the work of Gomory and Johnson from the 1970s. It has received renewed attention in the past few years. Recently Conforti, Cornu,jols, Daniilidis, Lemar,chal, and Malick proposed a general framework for studying cut-generating functions. However, they gave an example showing that not all cuts can be produced by cut-generating functions in this framework. They conjectured a natural condition under which cut-generating functions might be s...
-
作者：Izmailov, A. F.; Uskov, E. I.
作者单位：Lomonosov Moscow State University
摘要：In this paper we continue the studies of the persistent effect of attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers. It appears very important to understand the nature of this striking phenomenon, in particular, because it is precisely the reason of slow convergence of such methods when applied to problems with degenerate constraints. All previously known results concerned with this effect were a posteriori by nature: they were showing that in case of...
-
作者：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...
-
作者：Lan, Guanghui
作者单位：State University System of Florida; University of Florida
摘要：The main goal of this paper is to develop uniformly optimal first-order methods for convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. By incorporating a multi-step acceleration scheme into the well-known bundle-level method, we develop an accelerated bundle-level method, and show that it can achieve the optimal complexity for solv...
-
作者：Song, Wen; Xu, Xiaomei; Yao, Jen-Chih
作者单位：Harbin Normal University; Kaohsiung Medical University; King Abdulaziz University
摘要：In this note, we give a counterexample to show that the characterization formula for the condition numbers of a convex set of given in Coulibaly and Crouzeix (Math Program 116:79-113, 2009) is incorrect.
