# 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 if it isn't optimal to perform it on r1 and perform j2 on r1 only if it isn't optimal to perform it on r2.

In other words I would like to see an optimal solution

Resource r1 performs within H: j1, j1, j1, j1

Resource r2 performs within H: j2, j2, j2

rather than an optimal solution

Resource r1 performs within H: j1, j2, j2, j1

Resource r2 performs within H: j2, j1, j1

• Would you elaborate more on the problem specification? E.g. what you mean by I would like to see an optimal solution (1) rather than an optimal solution (2)? What is the actual difference between the first optimal and the second one from the objective function side? And how do you ensure both are optimal? Aug 4, 2023 at 22:20
• Suppose the problem is to perform once j1 and once j2 on r1 or r2 within the horizon H. The optimizer may return as the optimal solution a) perform j1 on r1 and j2 on r1 or b) perform j1 on r1 and j2 on r2 or c) perform j1 on r2 and j2 on r1 or d) perform j1 on r2 and j2 on r2. In this setting, I would like to impose such constraints that forbid a), c), d). In a more general problem involving many more j1, j2 case b may not be feasible so one of the other combinations should be allowed. So I need a statement that says forbid a), c), d) but only if b) is possible. Aug 5, 2023 at 19:12

Suppose you define a small penalty for each time a job is performed on the "wrong" resource. You now have a bicriterion optimization problem, one criterion being the original objective and the other being minimization of this penalty. There are at least three possible solution approaches.

1. Solve using the original objective only, constrain the original objective function to be no worse than the optimal value, and solve again with the objective being minimization of the penalty.
2. Add the penalty component to the original objective and solve one model. The catch with this approach is that you need to be able to scale the penalty component so that it cannot exceed in magnitude the difference between the (original) objective value of the optimal solution and the objective value of the best suboptimal solution.
3. Use a solver that is capable of handling lexicographic ordering of objective functions. (Recent versions of CPLEX, for instance, can do that.) The inherent idea is that nodes are pruned only if they are known to have a worse value of the original objective than does the incumbent or if they are known to tie the incumbent on the original objective but have a worse penalty value. So the problem is solved in a single branch-and-cut run, but with perhaps slower pruning of the search tree.
• The reason why I would like to impose the rule is that I would like to accelerate the solution of the problem. I would not bother implementing this rule if I were able to obtain the solution to the problem without this rule fast. I expect from the implementation of the rule a symmetry breaking effect and because of this shorter computation times. Because of this, suggestions 1 and 3 will not work. Suggestion 2 would probably work but I don't know if I could this way save computation time. Aug 4, 2023 at 20:46
• I suppose the way to answer the question would be to impose constraints that state: "W(j1,r2,t)=1 means j1 it cannot be performed on r1. It cannot be performed on r1 because r1 is occupied performing either j1 or j2 in the appropriate time slot". But would this suffice? Aug 4, 2023 at 21:27
• Let's assume that $W_{j,r, t}$ is a binary variable with value 1 signaling that job $j$ is on resource $r$ at time $t.$ It sounds like you might be looking for the following: $W_{j1,r2,t} + W_{j2,r1,t} \le 1 \, \forall t.$ That says that $j1$ cannot be on $r2$ at the same time that $j2$ is on $r1.$ Is this what you are after?
– prubin
Aug 4, 2023 at 22:10
• No, I am after the logic: j1 should not be on r2 if it can be on r1 (on an other possible optimal solution) . I expect that there are more than one equally good solutions to the problem. So, I would like to exclude some of them by introducing such requirements. Aug 5, 2023 at 13:09

The problem you have sounds like a parallel resource scheduling model that may have some additional limitations. $$(\text{R}_{2} \ | Cap | \sum_{j}w_{j})$$. In the simplest form, it is still NP-hard, I supposed there are two tasks and also two resources. I tried using a Generalized assignment problem, so already you can adapt it based on your formulation.

• Using appropriate costs/weights to assign tasks

\begin{align} & \text{Min} z = \sum_{i,j} x_{i,j}w_{i,j} \\ & \text{S.t:} \\ & \sum_{j} x_{ij} = 1 \quad \forall i \in \text{Task} \tag1 \\ & \sum_{i} x_{ij} \text{duration}_{i,j} \le Cap_j \quad \forall j \in \text{Resources} \tag2 \\ \end{align}

• Using an arbitrary binary assignment parameter/set

$$\sum_{j} x_{ij} \gamma_{i,j} = 1 \quad \forall i \in \text{Task} \tag1$$

Now, for two tasks with the following durations:

duration (i,j) 'resource usage'
R1    R2

alpha(i,j) 'resource assign'
R1  R2


the results of the two ways would be the same:

In addition to below constraints with binary assignment vars $$x$$

$$\sum_j x_{j,r,t} \le 1 \ \ \forall t,r$$
$$\sum_r x_{j,r,t} \le 1 \ \ \forall t,j$$

Define binary vars $$z_{j,r}$$ subject to

$$x_{j,r,t} - x_{j,r,t-1} \le z_{j,r}$$
$$x_{j,r,t-1} - x_{j,r,t} \le z_{j,r}$$
$$x_{j,r,t-1} + x_{j,r,t} + z_{j,r} \le 2$$

Define objective
$$\min \sum_{j,r}z_{j,r}$$