Symmetry problem among solutions

Answered

Arvi Tolvanen

April 22, 2021 22:32

• 
• 
• 

I got MIP model in which target function is constant and the goal is to find feasible variable solutions to that.

Lets say one feasible solution is = {A, B, C}, however every permutation of that is also a feasible solution. ({A,C,B},{B,A,C},....). Is there a way to ignore the permutations and find only the unique solutions?

(A,B,C are all n-length vectors)

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:56 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  April 23, 2021 11:23 Edited

  Hi Arvi,

  You could introduce symmetry breaking constraints. An example would be \(A \leq B \leq C \leq ...\) Since \(A,B,C\) are all vectors in your case, you could introduce constraints of the form \(\sum a_i \leq \sum b_i \leq ...\) There is also the case when some of these constraints are fulfilled with equality. If this applies to your problem, then you would have to come up with a different symmetry breaking constraint which accounts for this property, e.g., \(a_1 \leq b_1 \leq ...\)

  Best regards,
  Jaromił

  1
• 

  Arvi Tolvanen

  April 23, 2021 12:02

  • 
  • 
  • 

  Hi Jaromił,
  
  Thanks for your answer, that idea could work with some refining!
  
  However A, B, C can't monotonously be sorted cell-wise. Eg.
  A = (1,0,0,0,0,1,0,1,0)
  B = (0,1,0,1,0,0,0,0,1)
  C = (0,1,0,0,0,1,1,0,0)

   

  Now \(a_{1} \geq b_{1}\), but \(a_{2} \leq b_{2}\).
  
  also \(\sum a_{i} = constant\), for  A, B and C
  
  Partial solution could be (as you suggested) applying only \(a_{1} \leq b_{1} \leq ...\), but that would ignore all \(a_{2, ...}\) and others.
  
  Could there be a way to apply hierarchical sort with constraints? (Like arrange(*data*, "by _{1}", "by_{2}",...) in R dplyr)
  
  

  0
• 

  Jaromił Najman

  • Gurobi Staff

  April 23, 2021 13:11 Edited

  Hi Arvi,

  Could there be a way to apply hierarchical sort with constraints?

  I don't understand what you mean by a hierarchical sort with constraints. Could you elaborate?

  Would something like this work?

  \[\begin{align}
     a_n \leq b_n \leq &c_n \leq ... \\
     b_{n-1} \leq &c_{n-1} \leq ... \\
     &c_{n-2} \leq ...\end{align}\]

  Best regards,
  Jaromił

  0
• 

  Arvi Tolvanen

  April 23, 2021 18:59

  • 
  • 
  • 

  Hi! Hard to formally descibe it, but like this in excel:
  
  (first it sorts column A, then B, ...)

  

  0

Post is closed for comments.