0
$\begingroup$

I have an integer linear programming problem where i want to maximize over $\{0,1\}^n$, so i have the problem $$\max_{x \in \mathbb{R}^n}c^Tx, \text{ subject to } x_i \in \{0,1\} \text{ for all } i = 1,\dots, n.$$ I now want to introduce a constraint to make sure that the ones in the vector have specific distances $d_1,\dots, d_n$. This means, I want a constraint that assures that when $x_i = 1$, then $x_{i\pm j} = 0$ for all $j = 1, 2,\dots,d_i$. With this I want to make sure that the elements which are chosen (the ones) are not too close to eachother. I already found that when $d_i = 1$, I could formulate the constraint $0.5x_{i-1} + x_i + 0.5x_{i+1} \leq 1$. But already for $d_i = 2$ I was lost.

Does someone have an idea on how to do this? That would be awesome!

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can add the constraints $$x_i + x_j\leq 1 \quad\forall i, j = 1, ..., n, i\neq j, |i-j| \leq \max(d_i, d_j)$$

This is stronger than the constraints you propose, since for $d_i=1$, we will have the constraints $x_{i-1} + x_i \leq 1$ and $x_i + x_{i+1} \leq 1$. By summing these two inequalities, you obtain your proposed inequality.

$\endgroup$
3
  • $\begingroup$ Thank you!! that was quiet easy! I will try to formulate the problem like that and solve it in Matlab, I am optimistic it will work out. $\endgroup$ Commented Dec 6, 2023 at 0:27
  • $\begingroup$ You can obtain these "conflict" constraints via conjunctive normal form (CNF). You want to enforce $x_i \implies \lnot x_j$, which is equivalent to CNF $\lnot x_i \lor \lnot x_j$, which yields linear constraint $(1-x_i)+(1-x_j) \ge 1$, which simplifies to $x_i+x_j \le 1$. $\endgroup$ Commented Dec 6, 2023 at 1:46
  • 1
    $\begingroup$ Your $\min$ should instead be $\max$. $\endgroup$ Commented Dec 6, 2023 at 22:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.