Symmetry problem among solutions

回答済み

Arvi Tolvanen

2021年04月22日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:56 編集済み

  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

  2021年04月23日 11:23 編集済み

  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

  2021年04月23日 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

  2021年04月23日 13:11 編集済み

  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

  2021年04月23日 18:59

  • 
  • 
  • 

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

  

  0

投稿コメントは受け付けていません。