Linear Programming with Modulo Linear Constraints

Question

Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as:

find feasible point s.t.

$\min \sum_{ij}v_{ij}$

for all $(i,j)$ in $E$

$z_{ij} \le (c_i - c_j) \bmod k$ (i)

$z_{ij} \le (c_j - c_i) \bmod k$ (ii)

$z_{ij} + v_{ij} \ge 1$ (iii)

Think of the last as something like the soft margin constraint for an SVM.

In other words, all $c_i$ are real numbers and the absolute modulo $k$ difference between all adjacent $c_i,c_j$ must be greater than 1. It seems like a sensible notion of an update to de-violate constraints is to increase a given variable $c_i$ to make minimize the objective, then hop to a neighbor with infeasible edges and do the same, repeat, etc. Each greedy local update is natural.

What sort of issues would this formulation encounter if I tried to put it into practice? Could I get a reasonable approximation procedure from it, or would I be stuck with a heuristic, or is it likely to fall into some sort of weird cyclic behavior.

In general, what can I do and not do with modulo constraints for linear programming?

Answer 1

If one uses the standard notion of a "linear program", i.e., minimization of a linear functional over a polyhedral set, then it is not clear to me if your problem is actually a linear program. The constraint with the modulo function is equivalent to a disjunction of several affine constraints. This would in general make your problem nonconvex, and thus quite hard.

If you are willing to deal with an integer program, you can exploit the structure. You can write the modulo constraints as e.g., $c_i - c_j -\alpha_{ij} k \geq z_{ij}$, where $\alpha_{ij}$ is an integer for all $i,j$ and a new variable added to your problem. The resulting problem is a mixed integer linear program. Results/algorithms for these are based on the structure of the linear constraints. I am not an expert in MILPs, but I thought this may give you some pointers.