Questions tagged [symmetry]

For questions about invariance under transformations, in OR usually the transformation of a solution into other solutions of the same objective value.

Filter by
Sorted by
Tagged with
1 vote
3 answers
95 views

Breaking symmetry

Suppose resources r1 and r2 are both able to perform jobs j1 and j2. The duration of the jobs being done is d. I would like to model the following rule: Within a time horizon H, perform j1 on r2 only ...
Clement's user avatar
  • 2,224
6 votes
2 answers
227 views

Breaking symmetry of permutations in LIP

Setup I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using ...
armset's user avatar
  • 73
9 votes
2 answers
550 views

Dealing with Symmetry. Commercial solver defaults vs manual implementations

Since the modeler has domain/business knowledge of the problem being solved, is it possible to manually implement Isomorphism Pruning or Orbital branching and beat the default methods implemented by ...
user3711946's user avatar
3 votes
3 answers
252 views

Improving best bound within B&B process

Here is an extract from the BnB solution process of my problem. The solver determines a value of 2627.452494 as being the best bound of the optimal solution. The value for the best bound remains the ...
Clement's user avatar
  • 2,224
0 votes
0 answers
67 views

Excluding non-preferable solutions from a MILP

I have a model which delivers the following results (other combinations are also possible, all Xs have 50 as an upper bound): Case I $X1 = 50.0$ $X2 = 13.750$ $X3 = 50.0$ $X4 = 50.0$ Case II (obtained ...
Clement's user avatar
  • 2,224
7 votes
2 answers
168 views

How can preferences be modelled in MILPs?

Suppose a MILP model includes the following constraint: $ \begin{gather*} B_{1} + B_{2} + B_{3} \le 100 \end{gather*} $, where $B_{1},B_{2},B_{3}$ are nonnegative reals. Suppose that $\begin{...
Clement's user avatar
  • 2,224
13 votes
1 answer
265 views

Symmetry-breaking ILP constraints for square binary matrix

Setup I have a binary $N \times N$ matrix. The objective is to minimize the number of ones in the matrix, subject to various constraints. This leads to symmetries by rotating 90 degrees and/or ...
Simon's user avatar
  • 1,122
22 votes
5 answers
2k views

How can I best handle symmetries in my MIP?

When dealing with mixed-integer-programs with many symmetric solutions it can take very long until the branch-and-bound-tree search is finished because symmetric optimal solutions cannot be pruned. ...
YukiJ's user avatar
  • 2,013