Clearly, the cut is tightest for \(j = \arg \max_{j \in [m]} y_j\) (in which case \(y_j \geq \frac{1}{n}\) for normalised \(y\)), but it is valid for any other constraint.
Chubanov has an elementary proof that the unit-step dual ascent he proposes reduces (after normalising \(y\)) \(z(y)\) to at most \(k^{-1/2}\) after \(k\) iterations. We can achieve the same bound (or better) with a number of classical subgradient (gradient, with the unit ball constraint) methods; Peña and Soheili propose an accelerated multiplicative weight update method that improves the reduction to \(z(y) \leq k^{-1}\) after \(k\) iterations. Chubanov's analysis does not extend trivially to the 0/1 box, but we can still use non-accelerated subgradient methods to ensure an inverse square root decrease in \(z(y)\), or accelerated methods on smoothed subproblems to obtain a \(k^{-1}\) decrease.
In Chubanov's case, the inequality matrix is the identity, so we always get a valid inequality of the form \(0 \leq x_j \leq \frac{z(y)}{y_j} \leq n z(y)\). If we know that we are only interested in integer solutions, we can round down to \(0 \leq x_j \leq \left\lfloor \frac{z(y)}{y_j}\right\rfloor\), and usually fix the variable to 0. If we extend the inequality to be \(0 \leq x \leq t \mathbf{1}\), we can also directly fix variables to their upper bound (instead of setting slack variables to 0). Otherwise, we can expand the space for that variable only, and solve an updated subproblem that is still in the 0/1 box, with coordinate-wise rescaling.
In the general case, the inequality isn't as simple. The right-hand side is the same, but instead of an elementary vector, the constraint row \(g_j\) is a general vector. In some rare cases, we may be able to fix a single variable, if the right-hand side is tight enough. However, that seems unlikely. I see three options:
- Hope that we eventually generate a useful valid inequality for a box constraint;
- Reuse Peña and Soheili's space expansion transform;
- Reformulate some tight-ish inequality as equality + slack variable, and reduce the range of the slack variable.
The first option is a no-go for me (we can still use it heuristically). The second option seems like the most principled, but I'm not sure if there are more non-smooth optimisation methods with convergence bounds in term of the feasible (optimal?) volume; it also seem to change the primal solution space, although I wouldn't be surprised if it was equivalent to a step size tweak. The third one is less elegant, but it gives us a clear progress metric (either the range of some slack variable decreases geometrically, or we transform another inequality to equality + slack), and I feel like it might be the same thing as the space transform.