# Linear Programming with Modulo Linear Constraints

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?

• @Suresh: In MathJax and AMSLaTeX, \mod denotes “mod” with a large preceding space. Please use \bmod to denote “mod” used as a binary operator. – Tsuyoshi Ito Apr 21 '12 at 13:04

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.