A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture
by Derrick Stolee
Stephen Hartke and I recently uploaded our paper, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture to the arXiv. We build a computational method to verify a conjecture involving the number of nonnegative -sums in a nonnegative sum of real numbers. With this method, we proved a stronger statement than the conjecture for all and formed a stronger conjecture.
The method makes use of linear programming techniques and software, so begins our discussion of linear and integer programming methods. Read on to discover the method and also to figure out what is going on with the picture below.
The Conjecture and Past Work
The Manickam-Miklós-Singhi Conjecture. If , then every vector with nonnegative sum contains at least nonnegative -sums.
Bier and Manickam were the first to prove that exists, but had the very exponential bound
which was later improved incrementally by the following authors:
|Alon, Huang, Sudakov, ’12|
In this final reference, the trio of Alon, Huang, and Sudakov proved a quadratic upper bound, vastly improving over the previous exponential bounds. While these papers focused on the asymptotic bounds on , less has been done to determine exact values of .
|Marino, Chiaselotti, ’02|
We extend this direction by showing for all . We shall crucially use the following lemma of Chowdhury:
Lemma (Chowdhury) If , then .
From this lemma, we “only” need to determine for a finite number of values .
We now begin discussing our technique, which begins with a poset that arises after ordering our values as .
The Shift Poset
For the sake of our discussion, we will frequently identify a -set with the partial -sum . We define the shift poset on the -subsets of where for and when for all . We say is to the left of when (and is to the right of ). For example, see the following diagram of two such sets:
The reason for this ordering is that the partial sums have the ordering whenever . So, if we somehow “know” or “constrain” a sum to be nonnegative, all sums to the left are also nonnegative (and if a sum is strictly negative, all sums to the right are also negative).
We visualize the shift poset as a diamond, where the left-most set is on the left corner, the right-most set is on the right corner, and the largest antichain (which naturally sits somewhere halfway between these two extremes) stretches between the bottom and top corners, as below.
This poset has many nice properties, including being a lattice and also having the lexicographic and colexicographic orderings as linear extensions. Thus, our methods of iterating over all -sets using lex or colex play nice with the ordering. This is helpful for finding maximal or minimal sets under certain properties.
We use some notation to our advantage:
- is the set of all sets to the left of . Let .
- is the set of all sets to the right of . Let .
- For two collections and of -sets, define and .
Given a vector , the -sets partition into those with nonnegative -sum in and those with negative sum. This partition is split into a “left-closed” set and “right-closed” set. Have a picture:
Our goal, then, is to search for the partition first, and then the vector satisfying that partition. If there are fewer nonnegative sets than our target, then the vector will be a counterexample. Otherwise, when we fail to find a suitable partition (and vector), we have guaranteed that no counterexample exists. What is even better is that we can find exactly how many nonnegative -sums are guaranteed, even when the conjectured bound of does not apply.
Definition. Let be the minimum number of nonnegative -sums of a vector .
Our algorithm verifies that for some target value by searching for a vector with strictly fewer than nonnegative -sums. If none is found, the inequality is true.
A simple algorithm would be to brute-force test all partitions of -sets into two parts that are left- and right-closed, respectively. Moreover, we only need to test those with fewer than sets in the nonnegative part. However, we need to connect this finite, discrete problem with the continuous problem of vectors in . For this, we use linear programming.
Definition. Let be the linear program defined as
The importance of this linear program is that there is a feasible point for if and only if there is a vector with all sets in having nonnegative sum and all sets in having strictly negative sum.
Hence our algorithm proceeds as follows. At every search node, we have our collections and of nonnegative and negative sets. We select a -set that is not yet decided to be nonnegative or negative, and we branch by placing in one of these collections. This adds a constraint to the linear program (hence the “branch-and-cut” strategy) and we can test for feasibility. If the linear program is infeasible, we can prune the search tree. Otherwise, we test our optimal vector for having fewer than nonnegative -sums. If it is not a counterexample, we select again and branch.
One thing we can do very quickly is determine that no counterexample will be found when . Thus, if adding a set to would make this inequality hold, we can immediately add it to . We have a few methods for making this decision, and testing them efficiently was a nontrivial exercise.
Now, when we branch to make a set have nonnegative sum, this increases the number of sets we can guarantee to be strictly negative. These branches collapse the poset into a very small window of sets, and we quickly find the linear program infeasible. Click on the figure below for a larger view of this process:
However, we don’t get the advantage of this propagation when we branch to make a set negative. Instead, we continue adding negative sets until the linear program becomes infeasible (due to too many strictly negative sums while having a nonnegative total sum). This is still a finite amount of time, but it leads to a very unbalanced search tree, which is not ideal for parallelization.
To improve this issue of the unbalanced algorithm, we added the following propagation step: If branching a set to have negative sum makes the linear program infeasible, then make the set have nonnegative sum. This test can be run on all sets before any branching is done. However, this test is very time-consuming. For small cases, it leads to no branching at all, but quickly becomes intractable to test that many linear programs. So, we randomly sample sets that are not in either side of the partition and make this test. We continue sampling until either we make some number of samples and the test does not make a change or a time limit runs out. This last random step is a zero-error randomized algorithm (so it always gives the right answer, but the run time is a random variable) and allows us to stretch our computation to verify the conjecture for .
Results and New Conjecture
By implementing and executing our algorithm, we verify a stronger statement than the MMS conjecture and use that data to formulate a stronger conjecture. Here are the values of :