Slepian’s Inequality in Combinatorial Optimization

A 0-1 program is studied where linear objective function with uniformly distributed coefficients is maximized under arbitrary linear and/or non-linear constraints. Solving this problem a given number of times results in a sampling from the feasible set. Based on Slepian’s inequality, we prove that when this set has certain combinatorial properties, the sampling is uniform; otherwise the sampling is biased toward mutually orthogonal feasible solutions. This result allowed developing an effective heuristic for finding a maximum number of mutually orthogonal feasible solutions. Computer experiments illustrating the result are provided.