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

Optical Memory and Neural Networks

The binarization of the decision rule in the binary optimization problem

Boris Kryzhanovsky, Vladimir Kryzhanovsky

Published Mar 1, 2010• 0 citations
Publisher

Abstract

The study deals with minimization of a multiple-extremum quadratic functional defined in the state space of binary variables. In order to speed the computation of the local field (which is similar to the gradient in the continuous space), we offer binarization of the matrix on which the functional is built by substituting its elements with 0, +1, or −1 according to their signs. We show that the binarization can be performed so that the computed and real directions of the local field will very likely be the same. The algorithm is particularly useful for treating high-dimensionality configuration spaces because the binarization of the matrix considerably simplifies computations and decreases the amount of memory needed.

DOI
10.3103/s1060992x10010030

Related papers

Discretization of a matrix in quadratic functional binary optimization

Boris Kryzhanovsky, M. V. Kryzhanovsky, M. Yu. Malsagov

The capability of discretization of matrix elements in the problem of quadratic functional minimization with linear member built on matrix in N-dimensional configuration space with discrete coordinates is researched. It is shown, that optimal procedure of replacement matrix elements by the integer quantities with the limited number of gradations exist, and the efficient of minimization does not reduce. Parameter depends on matrix properties, which allows estimate the capability of using described procedure for given type of matrix, is found. Computational complexities of algorithm and RAM requirements are reduced by 16 times, correct using of integer elements allows increase minimization algorithm speed by the orders.

arXiv:1205.0732•Doklady Mathematics•Jun 1, 2011•5 citations

Attraction area of minima in quadratic binary optimization

Iakov Karandashev, Boris Kryzhanovsky

The paper deals with the problem of quadratic functional minimization in the space of binary variables. We analyze the efficiency of the random search procedure used in binary minimization and show that the radius of the attraction area of a minimum directly depends on its depth: the deeper the minimum, the greater its radius of attraction. Thus, the probability of finding a minimum during random search grows exponentially with depth of the minimum.

Optical Memory and Neural Networks•Apr 1, 2014•8 citations

Dimensionality reduction for binary quadratic programming problems

Rabih Battikh, Bilal Hammoud, Hassan Alabboud +2 more

Abstract This paper addresses the constrained binary quadratic problem (QP). This problem consists in minimizing a quadratic function a binary variables (0-1 variables) with linear constraints. Accordingly, in this work, We have generalized reliable fixing criteria (F0) and (F1) for the (QP) problem. The purpose of these fixing criteria is to facilitate the resolution of the initial problem (QP) where through these criteria we can decrease the dimension of the (QP) problem when it is possible and sometimes we can solve this problem completely by using a repeat loop based on these criteria (QPFA algorithm). Numerical results are presented to consolidate the demonstrated theoretical results and prove efficiency and performance in terms of speed, quality and robustness of our work. Mathematics Subject Classification: 90C20 , 90C27 , 90C10

•Aug 5, 2025•0 citations

New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences

Tavares, Gabriel

This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.

•Jan 1, 2008•7 citations

Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

David Bergman, Leonardo Lozano

In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each individual diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.

INFORMS journal on computing•Aug 14, 2020•10 citations

Decoding by local optimization (Corresp.)

K. Farrell, L. Rudolph, Carlos R. P. Hartmann +1 more

The maximum likelihood decoding problem for linear binary(n,k)codes is reformulated as a continuous optimization problem in ak-dimensional solid cube. We obtain a near optimum solution of this problem by use of a simple gradient local optimization algorithm. Computer simulation results are presented for the(21,11)projective geometry code and the(47,23)quadratic-residue code.

IEEE Transactions on Information Theory•Sep 1, 1983•19 citations
The study deals with minimization of a multiple-extremum quadratic functional defined in the state space of binary variables. In order to speed the computation of the local field (which is similar to the gradient in the continuous space), we offer binarization of the matrix on which the functional is built by substituting its elements with 0, +1, or −1 according to their signs. We show that the binarization can be performed so that the computed and real directions of the local field will very likely be the same. The algorithm is particularly useful for treating high-dimensionality configuration spaces because the binarization of the matrix considerably simplifies computations and decreases the amount of memory needed.
The capability of discretization of matrix elements in the problem of quadratic functional minimization with linear member built on matrix in N-dimensional configuration space with discrete coordinates is researched. It is shown, that optimal procedure of replacement matrix elements by the integer quantities with the limited number of gradations exist, and the efficient of minimization does not reduce. Parameter depends on matrix properties, which allows estimate the capability of using described procedure for given type of matrix, is found. Computational complexities of algorithm and RAM requirements are reduced by 16 times, correct using of integer elements allows increase minimization algorithm speed by the orders.
Abstract This paper addresses the constrained binary quadratic problem (QP). This problem consists in minimizing a quadratic function a binary variables (0-1 variables) with linear constraints. Accordingly, in this work, We have generalized reliable fixing criteria (F0) and (F1) for the (QP) problem. The purpose of these fixing criteria is to facilitate the resolution of the initial problem (QP) where through these criteria we can decrease the dimension of the (QP) problem when it is possible and sometimes we can solve this problem completely by using a repeat loop based on these criteria (QPFA algorithm). Numerical results are presented to consolidate the demonstrated theoretical results and prove efficiency and performance in terms of speed, quality and robustness of our work. Mathematics Subject Classification: 90C20 , 90C27 , 90C10
This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.
In recent years the use of decision diagrams within the context of discrete optimization has proliferated. This paper continues this expansion by proposing the use of decision diagrams for modeling and solving binary optimization problems with quadratic constraints. The model proposes the use of multiple decision diagrams to decompose a quadratic matrix so that each individual diagram has provably limited size. The decision diagrams are then linked through channeling constraints to ensure that the solution represented is consistent across the decision diagrams and that the original quadratic constraints are satisfied. The resulting family of decision diagrams are optimized over by a dedicated cutting-plane algorithm akin to Benders decomposition. The approach is general, in that commercial integer programming solvers can readily apply the technique. A thorough experimental evaluation on both benchmark and synthetic instances exhibits that the proposed decision diagram reformulation provides significant improvements over current methods for quadratic constraints in state-of-the-art solvers.