Search

Your search keyword '"separation problem"' showing total 4 results
Start Over Descriptor "separation problem" Journal mathematics of operations research
4 results on '"separation problem"'

1. SEPARATION OF PARTITION INEQUALITIES.

Author

Baïo, Mourad, Barahona, Francisco, and Mahjoub, Ali Ridha

Subjects
ALGORITHMS, FOUNDATIONS of arithmetic, SUBMODULAR functions, EQUATIONS, POLYTOPES, HYPERSPACE
Abstract

Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a partition inequality is of the x(δ(S1… ,Sp)≥ ap + b. Here δ(S1 Sp) denotes the multicut defined by a partition S1….Sp of V. Partition inequalities arise as valid inequalities for optimization problems related to A-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x(δ(S1…Sp))- p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities. [ABSTRACT FROM AUTHOR]

Published
2000
Full Text
View/download PDF

2. Cut-Generating Functions and S-Free Sets

Author

Michele Conforti, Gérard Cornuéjols, Claude Lemaréchal, Jérôme Malick, Aris Daniilidis, Laboratoire de Physique des Lasers, Atomes et Molécules - UMR 8523 (PhLAM), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Tepper School of Business, Carnegie Mellon University [Pittsburgh] (CMU), Departament de Matemàtiques [Barcelona] (UAB), Universitat Autònoma de Barcelona (UAB), Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems (BIPOP), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann (LJK), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)

Subjects
Discrete mathematics, Convex analysis, Generalized gauges, Optimization problem, Theory, General Mathematics, Integer programming, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Management Science and Operations Research, Complementarity (physics), Separation, Computer Science Applications, Linear map, S-free sets, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics, Separation problem
Abstract

International audience; We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (cgf) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to S-free sets and we study this relation, disclosing several definitions for minimal cgf's and maximal S-free sets. Our work unifies and puts in perspective a number of existing works on S-free sets; in particular, we show how cgf's recover the celebrated Gomory cuts.

Published
2015

3. Separation of Partition Inequalities

Author

Francisco Barahona, Ali Ridha Mahjoub, and Mourad Baïou

Subjects
Discrete mathematics, Combinatorics, Optimization problem, General Mathematics, Partition (number theory), Management Science and Operations Research, Polynomial algorithm, Computer Science Applications, Separation problem, Mathematics, Submodular set function
Abstract

Given a graph G = (V, E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x(δ(S1,…,Sp)) ≥ ap + b. Here δ(S1,…,Sp) denotes the multicut defined by a partition S1,…,Sp of V. Partition inequalities arise as valid inequalities for optimization problems related to k-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x(δ(S1,…,Sp)) − p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities.

Published
2000

Catalog

Books, media, physical & digital resources
See catalog results