Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Kluwer Academic Publishers eBooks

Branch and Cut Algorithm for QCL-C

Published May 31, 2006• 0 citations
Publisher
DOI
10.1007/0-387-23532-9_9

Related papers

A branch-and-cut algorithm for Mixed-Integer Bilinear Programming

Matteo Fischetti, Michele Monaci

European Journal of Operational Research•Sep 26, 2019•38 citations

QCL-C: Relaxations and Special Cases

Kluwer Academic Publishers eBooks•May 31, 2006•0 citations

QCL-C: Formulations and Projection Inequalities

Kluwer Academic Publishers eBooks•May 31, 2006•0 citations

A Note on the Branch-and-Cut Approach to Decoding Linear Block Codes

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP). Since it is an NP-hard problem in general, there are many researches about the algorithms to approximately solve the problem. One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al. LP decoding is based on the LP relaxation, which is a method to approximately solve the ILP corresponding to the ML decoding problem. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed by Taghavi et al. and Yang et al., respectively. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-and-bound methods. The branch-and-cut method is widely used to solve ILP, however, it is unobvious that the method works well for the ML decoding problem. In this paper, we show that the branch-and-cut method is certainly effective for the ML decoding problem. Furthermore the branch-and-cut method consists of some technical components and the performance of the algorithm depends on the selection of these components. It is important to consider how to select the technical components in the branch-and-cut method. We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2010•3 citations

Q-computation

Lajos Diósi

Springer eBooks•Feb 18, 2007•0 citations

Minimum distance computation of LDPC codes using a branch and cut algorithm

Ahmet Burak Keha, Tolga M. Duman

We give a branch-and-cut algorithm for finding the minimum distance of a binary linear block code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on turbo and low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts. We demonstrate that our IP formulation and specific cuts are efficient tools for determining the minimum distance of moderate size linear block codes, specifically, they are very efficient for LDPC codes, and provide us with an additional tool for solving this important problem.

IEEE Transactions on Communications•Mar 30, 2010•20 citations
Maximum likelihood (ML) decoding of linear block codes can be considered as an integer linear programming (ILP). Since it is an NP-hard problem in general, there are many researches about the algorithms to approximately solve the problem. One of the most popular algorithms is linear programming (LP) decoding proposed by Feldman et al. LP decoding is based on the LP relaxation, which is a method to approximately solve the ILP corresponding to the ML decoding problem. Advanced algorithms for solving ILP (approximately or exactly) include cutting-plane method and branch-and-bound method. As applications of these methods, adaptive LP decoding and branch-and-bound decoding have been proposed by Taghavi et al. and Yang et al., respectively. Another method for solving ILP is the branch-and-cut method, which is a hybrid of cutting-plane and branch-and-bound methods. The branch-and-cut method is widely used to solve ILP, however, it is unobvious that the method works well for the ML decoding problem. In this paper, we show that the branch-and-cut method is certainly effective for the ML decoding problem. Furthermore the branch-and-cut method consists of some technical components and the performance of the algorithm depends on the selection of these components. It is important to consider how to select the technical components in the branch-and-cut method. We see the differences caused by the selection of those technical components and consider which scheme is most effective for the ML decoding problem through numerical simulations.
We give a branch-and-cut algorithm for finding the minimum distance of a binary linear block code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on turbo and low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts. We demonstrate that our IP formulation and specific cuts are efficient tools for determining the minimum distance of moderate size linear block codes, specifically, they are very efficient for LDPC codes, and provide us with an additional tool for solving this important problem.