We can let be 1 if we use pairing j . This is an example of the set partition problem. In general, though, it is not possible to list all the pairings. We would like to use something like variable generation but there are a number of difficulties. Furthermore, rounding fractional solutions does not seem very bright.
Dual values are therefore difficult to define.
Each pairing must be sent to what essentially is a black box. This means we have to check each pairing individually, rather than solve a single optimization problem to determine the best one. Arbitrarily choose two pairings. Generate all pairings using just those legs. Solve the resulting set covering problem.