Binary Matrix Multiplication

Ongoing

Mahnoor Naseer

February 18, 2025 16:28 Edited

• 
• 

Hello,

I would like to ask what efficient models does gurobi community suggest when modelling matrix multiplication in mod 2 involving large binary matrices say 32x32. I have tried the multi xor modeling and piece wise modeling. Both ways the models turn out to converge very slow towards an optimal bound.

Any suggestions in this regard would be helpful.

Thank you.

Related to

• Best Bound

0

• 

  Bot Marley (with AI contributions)

  February 19, 2025 23:19

  • 
  • 

  Hi Mahnoor,

  When modeling matrix multiplication in mod 2 with large binary matrices (e.g., 32x32), the challenge lies in efficiently handling the XOR operations, which introduce nonlinearity and complexity into the optimization problem. Gurobi's strength lies in linear and mixed-integer programming, so translating the problem into a form that the solver can handle efficiently is crucial. Here are some approaches that might improve performance:

  🔢 Problem Analysis

  The matrix multiplication in mod 2 is essentially:

  C=A⋅Bmod  2

  where:

  • A and B are binary matrices (entries are 0 or 1).
  • C is the resulting binary matrix.
  • The operations involved are addition and multiplication under modulo 2, where addition is effectively XOR and multiplication is AND.

  🚦 Modeling Strategies

  1. Multi-XOR Modeling

  This is a common approach where you model each element of the resulting matrix using XOR constraints. If Cij is the element at row i and column j of the result:

  Cij=⨁k=1n(Aik∧Bkj)

  While straightforward, this can introduce many auxiliary variables and constraints, potentially leading to slow convergence.

  2. Piecewise Linear Modeling

  By breaking down the XOR into linear constraints, this method can reduce the complexity of non-linearities but might still suffer from slow performance, particularly with larger matrices.

  3. Alternative: Aggregated XOR Approach

  One optimization trick is to aggregate XOR operations to reduce the total number of variables and constraints:

  • Compute row-wise and column-wise "parities" in a hierarchical or block-wise manner.
  • Use Gurobi's native support for XOR constraints (addGenConstrXor) to handle these parities more directly.

  4. Column Generation or Decomposition Techniques

  If your problem allows it, you could decompose the matrix multiplication into smaller subproblems that can be solved independently and combined. This can sometimes drastically improve performance.

  5. Constraint Programming Hybrid

  For highly combinatorial XOR-heavy models, combining Gurobi's MILP solver with a constraint programming (CP) solver might help. This hybrid approach can manage logical constraints more natively.

  🧠 Practical Suggestion

  • Symmetry Breaking: Adding constraints to break symmetrical solutions can reduce the solution space.
  • Warm Starts: If solving a sequence of related problems, provide warm starts to Gurobi to speed up convergence.
  • Parameter Tuning: Experiment with parameters like NoRelHeurTime, MIPFocus, Cuts, Heuristics, and Presolve.

  - Bot

  Ask Gurobot a question!

  1
• 

  Mahnoor Naseer

  February 20, 2025 15:59

  • 
  • 

  Hi,

   

  So I was looking at your suggestion on using  (addGenConstrXor), gurobi 12.0.1 does nos support any such model constructor https://docs.gurobi.com/projects/optimizer/en/current/reference/python/model.html#Model.addGenConstrOr

   

  0

Please sign in to leave a comment.