We study a non-contiguous channelisation problem arising in multi-beam
geostationary satellite communications. Carriers have heterogeneous sub-
channel demands and priorities; carriers within the same beam cannot share
a subchannel, while reuse across beams is permitted subject to carrier-
specific cumulative-interference budgets. Demand may be partially satis-
fied, with a priority-weighted objective favouring higher-priority tra!c when
spectrum or interference constraints are binding.
We formulate the problem as a compact mixed-integer program and de-
rive an equivalent pattern formulation that removes subchannel-permutation
symmetry. Building on this formulation, we develop a pattern-based Price-
and-Branch algorithm combining randomized Greedy seeding, dual-guided
screening of a Greedy-generated pattern pool, and an exact mixed-integer
pricing problem, which we show to be NP-hard. We also develop two alter-
native methods: a Greedy-Seeded Relax-and-Cut algorithm and a Pairwise
Co-occurrence and Clique Reconstruction heuristic.
Computational experiments on eight industry-informed synthetic instances
and 30 controlled perturbations show that Price-and-Branch returns a fea-
sible solution on all 38 instances and attains the best or tied-best objective
on 37. For the 22 instances with certified column-generation convergence,
the median certified optimality gap is 0.06%. The results demonstrate ro-
bust performance under perturbations of interference tolerances and carrier
populations.