Pruning by isomorphism in branch-and-cut | Zendy

F. Margot | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Pruning by isomorphism in branch-and-cut

Author(s) -

F. Margot

Publication year - 2002

Publication title -

mathematical programming

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 2.358

H-Index - 131

eISSN - 1436-4646

pISSN - 0025-5610

ISBN - 3-540-42225-0

DOI - 10.1007/s10107-002-0358-2

Subject(s) - mathematics , pruning , backtracking , integer (computer science) , branch and cut , enumeration , combinatorics , group (periodic table) , isomorphism (crystallography) , branch and bound , tree (set theory) , integer programming , set (abstract data type) , algorithm , discrete mathematics , computer science , chemistry , crystal structure , agronomy , crystallography , biology , organic chemistry , programming language

The paper presents a Branch-and-Cut for solving (0, 1) integer linear programs having a large symmetry group. The group is used for pruning the enumeration tree and for generating cuts. The cuts are non standard, cutting integer feasible solutions but leaving unchanged the optimal value of the problem. Pruning and cut generation are performed by backtracking procedures using a Schreier-Sims table for representing the group. Applications to the generation of covering designs and error correcting codes are presented.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research