<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-21T21:53:58.320Z
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?
Elliot JJ
CC BY-SA 3.0
2012-04-21T23:27:59.103Z
Edited the above answer with a reply to this question.
Ankur
CC BY-SA 3.0
2012-04-21T20:30:06.173Z
2012-04-21T23:26:17.967Z
2012-04-21T23:26:17.967Z
Ankur
<p>Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as:</p>

<p>find feasible point s.t.</p>

<p>$\min \sum_{ij}v_{ij}$</p>

<p>for all $(i,j)$ in $E$</p>

<p>$z_{ij} \le (c_i - c_j) \bmod k$ (i)</p>

<p>$z_{ij} \le (c_j - c_i) \bmod k$ (ii)</p>

<p>$z_{ij} + v_{ij} \ge 1$ (iii)</p>

<p>Think of the last as something like the soft margin constraint for an SVM.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-04-21T13:04:40.643Z
@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
<ds.algorithms><graph-theory><graph-algorithms><optimization><linear-programming>
Linear Programming with Modulo Linear Constraints
Elliot JJ
# Linear Programming with Modulo Linear Constraints

(Asked by: username_0 on 2012-04-20)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, optimization, linear-programming

> **Comments:**
> **username_1**: @Suresh: In MathJax and AMSLaTeX, `\mod` denotes “mod” with a large preceding space.  Please use `\bmod` to denote “mod” used as a binary operator.  

---

## 1 answers

### Answer by username_2 on 2012-04-21. Score: 2

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: Edited the above answer with a reply to this question.  

---

