A linear programming approach to the Manickam–Miklós–Singhi conjecture

The Manickam–Miklós–Singhi conjecture states that when n≥4kn≥4k, every multiset of nn real numbers with nonnegative total sum has at least (n−1k−1)kk-subsets with nonnegative sum. We develop a branching strategy using a linear programming formulation to show that verifying the conjecture for fixed values of kk is a finite problem. To improve our search, we develop a zero-error randomized propagation algorithm. Using implementations of these algorithms, we verify a stronger form of the conjecture for all k≤7k≤7.