-
作者：Aissi, Hassene; Mahjoub, A. Ridha; McCormick, S. Thomas; Queyranne, Maurice
作者单位：Universite PSL; Universite Paris-Dauphine; University of British Columbia; Universite Catholique Louvain
摘要：We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear piec...
-
作者：Lee, Jon; Vygen, Jens
作者单位：University of Michigan System; University of Michigan; University of Bonn
-
作者：Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.
作者单位：Microsoft; Cornell University; Massachusetts Institute of Technology (MIT)
摘要：We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We introduce novel lower bounds based on packing trees, as well as a new decomposition technique that contracts entire regions of the graph while preserving optimality guarantees. Our a...
-
作者：Awate, Yogesh; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：Carnegie Mellon University; University of Waterloo
摘要：We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type 2 triangle (resp. Type 3 triangle; quadrilateral) inequalities, are all within a factor of of the integer hull, and provide examples showing that the approximation factor is not less than . There is ...
-
作者：Wang, Mengdi; Bertsekas, Dimitri P.
作者单位：Princeton University; Massachusetts Institute of Technology (MIT)
摘要：We consider the solution of strongly monotone variational inequalities of the form , for all . We focus on special structures that lend themselves to sampling, such as when is the intersection of a large number of sets, and/or is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems...
-
作者：Ostrowski, James; Anjos, Miguel F.; Vannelli, Anthony
作者单位：University of Tennessee System; University of Tennessee Knoxville; Universite de Montreal; Universite de Montreal; Polytechnique Montreal; University of Guelph
摘要：The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of mixed integer linear programming problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In this paper we show how to strengthen orbital branching in order to exp...
-
作者：Lehrer, Ehud; Teper, Roee
作者单位：Tel Aviv University; INSEAD Business School; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：The extension of set functions (or capacities) in a concave fashion, namely a concavification, is an important issue in decision theory and combinatorics. It turns out that some set-functions cannot be properly extended if the domain is restricted to be bounded. This paper examines the structure of those capacities that can be extended over a bounded domain in a concave manner. We present a property termed the sandwich property that is necessary and sufficient for a capacity to be concavifiabl...
-
作者：Dobre, Cristian; Vera, Juan
作者单位：Wageningen University & Research; Tilburg University
摘要：Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable conseque...
-
作者：Cornuejols, Gerard; Schaefer, Andrew
作者单位：Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
-
作者：Ben-Tal, Aharon; den Hertog, Dick; Vial, Jean-Philippe
作者单位：Technion Israel Institute of Technology; Tilburg University; Tilburg University
摘要：In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It turns out that to do so one has to calculate the support function of the uncertainty set and the concave conjugate of the nonli...
