Let $x_1, \dots, x_5, y_1, \dots, y_4$ be a total of nine variables taking values merely in $\{0, 1\} \subset \Bbb{Z}$. Therefore a solution is a point on a hypercube.
These are the constraint equations: $$ x_1 + x_2 + y_1 + y_2 = 1 \\ x_2 + x_3 + y_1 + y_2 + y_3 = 1 \\ x_3 + x_4 + y_2 + y_3 + y_4 = 1 \\ x_4 + x_5 + y_3 + y_4 = 1 $$
That I want to solve, while at the same time minimizing (something like): $$ x_1 + \dots + x_5 + y_1 + \dots + y_4 $$
The system alone can be solved in terms of 5 parameters in $\{0, 1\}$. That's $2^5$ possibilities to check in the naive worst case. This generalizes therefore not to a polynomial time algorithm.
Can we make use of symmetry somehow since the 1st and the last constraint equation are essentially the same. I don't know how to formally make use of that symmetry though...
Thus, how do I minimize the sum of the components of the hypercube under more variables than equations, in polynomial time with respect to $n$ the number of variables?
I can't think of any more constraints to my problem, but the problem this corresponds to is computing at least one smallest grammar of $s = aaaaaa$. Symmetries here are obvious since $Aaaaa$ and $aaaaA$ would be two distinct choices in an algorithm that are actually symmetric, so that you can skip one.
The constraint equations can be derived for example by noting that $x_i \in \{0, 1\}$ is whether the $i$th occurence of $aa$ within $s$ (starting from the left), and if it's present, it cancels out the presence of the 2nd $aa$ since they intersect. $y_i$ is whether the $i$th occurence of $aaa$ is present. By present I mean in a general grammar for $s$ that a solution then describes.
This is an instance of SET COVER, which is NP-complete. But with this structured version, you can pick $y_{2+3k}$ and then if that doesn't cover everything then one of the $x_j$ will cover the remaining one or two constraints.