I'm trying to use ILP to solve the following problem:
A series of connected nodes are provided. For the example below, $a$ is only connected to $b$, $b$ is connected to both $a$ and $c$, $c$ is connected to both $b$ and $d$, and $d$ is only connected to $c$. I want to place the four nodes in a matrix to minimize the required columns while maintaining connectivity. The constraint is the row number of the matrix, in this example, the row number is $3$.
The other constraint is the higher index node cannot be placed in an earlier column. For example, $d$ can only be placed in the same column or a later column than $a$.
Two possible solutions are below, where the column number is reduced to $2$:
An invalid solution is below, where $a$ cannot connect to $d$:
To use ILP, I assign each node with a row and column value. For example, $a$ is $(X_a,Y_a)$. The constraints can be set as:
\begin{align} &\text{minimize} & X_d\\ &\text{subject to} & Y_a, Y_b, Y_c, Y_d &\le 3 \tag1\label1\\ &&X_b - X_a &\ge 0 \tag2\label2 \\ &&X_c - X_b &\ge 0 \tag3\label3 \\ &&X_d - X_c &\ge 0 \tag4\label4 \\ &&X_b + Y_b - X_a - Y_a &= \pm 1 \tag5\label5 \\ &&X_c + Y_c - X_b - Y_b &= \pm 1 \tag6\label6 \\ &&X_d + Y_d - X_c - Y_c &= \pm 1 \tag7\label7 \\ &&X_c + Y_c - X_a - Y_a &\text{$> 1$ or $<-1$} \tag8\label8 \\ &&X_d + Y_d - X_a - Y_a &\text{$> 1$ or $<-1$} \tag9\label9 \\ &&X_d + Y_d - X_b - Y_b &\text{$> 1$ or $<-1$} \tag{10}\label{10} \end{align}
Constraint \eqref{1} sets the limit of the row number, constraints \eqref{5}-\eqref{7} set the connectivity, and the constraints \eqref{8}-\eqref{10} avoid the illegal connection.
I have two questions.
- Is the $1$ or $-1$ constraint valid for an ILP solver?
- The constraints that avoid illegal connectivity seem not scalable because it requires $n\log(n)$ constraints. Is there a better way to set this constraint?
You cannot directly enforce a disjunction with ILP, but you can use a binary variable to do so. For example, for your first constraint, introduce binary variable $Z_{ab}\in\{0,1\}$ and rewrite as equality constraint $$X_b + Y_b - X_a - Y_a = 2Z_{ab}-1.$$
Having said that, a more natural formulation would use a binary variable $x_i$ for each node, a binary variable $y_{ij}$ for each directed arc (which can go only up, down, or right), and binary variables $s_i$ and $t_i$ to indicator the source and sink, respectively. The constraints are as follows.
Select four nodes: $$\sum_i x_i = 4$$
Select one source node: $$\sum_i s_i = 1$$
Select one sink node: $$\sum_i t_i = 1$$
Source or sink implies selected: $$s_i + t_i \le x_i$$
Each selected node other than the last has exactly one outgoing arc: $$\sum_j y_{ij} = x_i - t_i$$
Each selected node other than the first has exactly one incoming arc: $$\sum_j y_{ji} = x_i - s_i$$
To enforce the "induced subgraph" rule, impose a constraint that two adjacent selected nodes must have a selected arc: $$x_i + x_j - 1 \le y_{ij} + y_{ji}$$
The objective is to minimize $\sum_i c_i t_i$, where $c_i$ is the column of node $i$.