0
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ I understand this, but but my program has a nice succinct representation, as opposed to actually representing it as disjunctive programming. Do I gain from this? $\endgroup$ – Elliot JJ Apr 21 '12 at 21:53
  • $\begingroup$ Edited the above answer with a reply to this question. $\endgroup$ – Ankur Apr 21 '12 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.