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.
8 questions
1
vote
3
answers
112
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 ...
- 2,300
6
votes
2
answers
243
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 ...
- 73
9
votes
2
answers
606
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 ...
- 305
3
votes
3
answers
331
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 ...
- 2,300
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 ...
- 2,300
7
votes
2
answers
184
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{...
- 2,300
13
votes
1
answer
279
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 ...
- 1,142
23
votes
5
answers
3k
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.
...
- 2,043