Finding the optimal offset for periodic signals to minimize concurrent transmissions

Question

I have a system with discrete time, that sends periodic signals with the following periods: [10, 20, 30, 40, 50, 100, 200, 500, 1000, 5000]. The number of signals belonging to each period is as follows [44, 10, 13, 22, 13, 21, 42, 3, 9, 1]

For example, 44 signals have the period 10 and are sent in the time cycles 0, 10, 20 and so on.

Problem description:

I want to give all signals having the same period (called as "signal class") a certain offset (ranging anywhere from 0 to period/2), so that at any given time the number of signals sent together is the lowest (compared to other offsets). Note that all signals having the same period will also have the same offset.

My original approach:

I used Python and tried a brute force approach to simulate each scenario and calculate the minimum number of parallel transmissions in each case. However, if you consider all possible offsets of all classes, there are 585937500000000000 different combinations to calculate. And that is not feasible. Even with a working brute force approach, more collisions can occur in arbitrary future, and the final result is not mathematically proven.

Can someone please help me to find a feasible approach to solve the problem? A solution in the form of pseudo-code or Python is also very welcome.

Answer 1

Taking all offsets to be $0$ would yield $$44 + 10 + 13 + 22 + 13 + 21 + 42 + 3 + 9 + 1 = 178$$ concurrent signals at every multiple of $$\operatorname{lcm}(10, 20, 30, 40, 50, 100, 200, 500, 1000, 5000) = 15000$$ cycles.

Via mixed integer linear programming (MILP), you can instead achieve a minimax value of $44$ concurrent signals by selecting the following offsets:

  10 3 
  20 0 
  30 0 
  40 1 
  50 0 
 100 1 
 200 4 
 500 0 
1000 2 
5000 0 

Here is the MILP formulation I used. Let $P$ be the set of periods. For $p\in P$, let $n_p$ be the number of signals and let $O_p=\{0,1,\dots,p/2\}$ be the set of offsets. Let $T=\{0,1,\dots,\operatorname{lcm}{P}\}$ be the planning horizon. Let binary decision variable $x_{po}$ indicate whether period $p$ uses offset $o$. Let $z$ represent the maximum number of concurrent signals across the planning horizon. The problem is to minimize $z$ subject to \begin{align} \sum_{o\in O_p} x_{po} &= 1 &&\text{for $p\in P$} \tag1\label1 \\ \sum_{p\in P} \sum_{\substack{o\in O_p:\\ t \equiv o \pmod p}} n_p x_{po} &\le z &&\text{for $t\in T$} \tag2\label2 \end{align}

Constraint \eqref{1} selects one offset per period. Constraint \eqref{2} linearizes the minimax objective; the left-hand side is the number of signals at time $t$.

For your given data, the optimal objective value turns out to be $z=44$, achieved for example by $$x_{10,3}=x_{20,0}=x_{30,0}=x_{40,1}=x_{50,0}=x_{100,1}=x_{200,4}=x_{500,0}=x_{1000,2}=x_{5000,0}=1.$$ Here is a plot of the resulting number of concurrent signals per time:

Note that there are many optimal solutions. I used a secondary objective to minimize the total amount of offset $\sum_{p\in P} \sum_{o\in O_p} o\cdot x_{po}$, which turns out to be $3+1+1+4+2=11$ for your given data.

Answer 2

Thanks to @RobPratt's approach, I was able to create the following Python script that solved the problem in a flash. I also made the additional constraint to keep the offsets as low as possible. For those who are interested, here is the code:

import pulp
from math import gcd
from functools import reduce

# Function to calculate lcm of a list of numbers
def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(lst):
    return reduce(lcm, lst)

# Define the periods and corresponding number of signals
periods = [10, 20, 30, 40, 50, 100, 200, 500, 1000, 5000]
num_signals = [44, 10, 13, 22, 13, 21, 42, 3, 9, 1]

# Calculate the planning horizon
planning_horizon = lcm_list(periods)

# Step 1: Minimize the maximum number of concurrent signals
prob1 = pulp.LpProblem("Minimize_Max_Concurrent_Signals", pulp.LpMinimize)

# Define the binary decision variables x_po
x = pulp.LpVariable.dicts("x", (periods, range(max(periods) // 2 + 1)), cat='Binary')

# Define the variable for the maximum number of concurrent signals
z = pulp.LpVariable('z', lowBound=0, cat='Continuous')

# Objective function: Minimize z
prob1 += z

# Constraint 1: Each period uses exactly one offset
for p in periods:
    prob1 += pulp.lpSum(x[p][o] for o in range(p // 2 + 1)) == 1

# Constraint 2: Linearize the minimax objective
for t in range(planning_horizon):
    prob1 += pulp.lpSum(num_signals[i] * x[periods[i]][o] for i in range(len(periods)) for o in range(periods[i] // 2 + 1) if t % periods[i] == o) <= z

# Solve the first problem
prob1.solve()

# Get the minimum value of z
min_z = pulp.value(z)

# Step 2: Minimize the sum of offsets with fixed z
prob2 = pulp.LpProblem("Minimize_Sum_Offsets", pulp.LpMinimize)

# Define the objective function: Minimize the sum of offsets
prob2 += pulp.lpSum(o * x[p][o] for p in periods for o in range(p // 2 + 1))

# Add the constraints from the first problem
for p in periods:
    prob2 += pulp.lpSum(x[p][o] for o in range(p // 2 + 1)) == 1

for t in range(planning_horizon):
    prob2 += pulp.lpSum(num_signals[i] * x[periods[i]][o] for i in range(len(periods)) for o in range(periods[i] // 2 + 1) if t % periods[i] == o) <= min_z

# Solve the second problem
prob2.solve()

# Print the optimal offsets
optimal_offsets = {p: o for p in periods for o in range(p // 2 + 1) if pulp.value(x[p][o]) == 1}
print(f"Optimal offsets: {optimal_offsets}")

# Print the minimized maximum number of concurrent signals
print(f"Minimized maximum number of concurrent signals: {min_z}")

# Print the minimized sum of offsets
min_sum_offsets = sum(o * pulp.value(x[p][o]) for p in periods for o in range(p // 2 + 1))
print(f"Minimized sum of offsets: {min_sum_offsets}")