2
$\begingroup$

I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not needed for this StackExchange question.

Suppose we have in input a set of nodes $V=\{1,\dots,n\}$ for $n\in \mathbb N,n\ge 4$, a subset $\widetilde V\subset V$, a symmetrical matrix of costs $s\in\mathcal M_n(\mathbb R)$ and a boolean vector $\hat{y}\in\{0,1\}^n$.

My (partial) problem is:

$\text{Min} \displaystyle \sum_{i\in V}\sum_{j\in V\setminus\{i\}}s_{ij}y_{ij}$

$s.t. \displaystyle\sum_{\substack{j \in V \backslash\widetilde{V}\\ i\neq j}} 2 y_{ij} + \displaystyle\sum_{\substack{j \in \widetilde{V}\\ i\neq j}} y_{ij} = 2(1 - \hat{y}_{i}) \quad \forall i \in V$

$\quad y_{ij}\le \hat y_{j}\quad \forall (i,j)\in V^2, i\neq j$

$y_{ij}\in \{0,1\},\quad \forall (i,j)\in V^2,i\neq j,\quad(*)$

Currently the constraints are Integer and Linear. And the following example shows that using

$y_{ij}\in [0,1],\quad \forall (i,j)\in V^2,i\neq j,\quad (**)$

is not enough to make it linear. Indeed, suppose that $V = \{1,2,3,4\}$:

  • $s_{41} = 12$
  • $s_{42} = 1$
  • $s_{43} = 10$
  • $\hat{y}=[1,1,1,0]$
  • $1\notin \widetilde V$ and $2\in \widetilde V$ as well as $3\in \widetilde V$

Using $(*)\;\,$ and focusing on node $4$ will give an optimal (partial) solution of $y_{42} = y_{43} = 1 = 1 - y_{41}$ of cost $11$.

Using $(**)$ and focusing on node $4$ will give an optimal (partial) solution of $y_{41} = y_{42} = 0.5$ and $y_{43} = 0$ of cost $6.5$ which is better than with $(*)$ and feasible for all constraints except integer constraints $(*)$.

I don't know how I should linearize such constraints? Thank you for your kind help :D

EDIT: thanks to @Kuifje's comments, I want the same problem but with linear decision variables instead of $y_{ij}\in \{0,1\}$. Using $y_{ij}\in[0,1]$ is not enough as shown in the 4 nodes example. I believe the linearization is possible because I have a polynomial algorithm solving the problem.

EDIT 2: I don't know if it is going to help:

The ILP you have above models a graph theory problem where, given a set of nodes $V$ and a subset $\widetilde V$. Suppose that $\hat{y}_i$ will be $1$ if and only if $i$ is selected. We will try to minimize, for all non selected hubs $i$, the minimum between

  • the distance between $i$ and the closest selected hub in $V\setminus{\widetilde V}$
  • and the sum the two distances between $i$ and the two closest selected hubs in $\widetilde V$
$\endgroup$
7
  • $\begingroup$ I am not sure I follow : you want to get rid of the integer variables ? What makes you think this is possible ? If the problem is NP-hard, you will not be able to formulate it as a pure linear problem (or else you will become very famous). $\endgroup$
    – Kuifje
    Oct 12 at 14:29
  • $\begingroup$ @Kuifje, yes, I would like to know how I could get rid of the integer constraints and have linear instead. I believe it is possible because I have a polynomial algorithm solving the problem. If it is not possible, there should be a mistake in my polynomial algorithm (I am not going to prove anything on P=NP haha) but I don't think it is the case $\endgroup$
    – JKHA
    Oct 12 at 14:32
  • $\begingroup$ Ok, I understand. In this case, I think you will get better answers if you show your full problem in detail. There may be a linear formulation (assuming your polynomial algorithm is correct), but it may be quite different than yours. $\endgroup$
    – Kuifje
    Oct 12 at 14:34
  • $\begingroup$ @Kuifje, I think what I have shown in the post is enough, I have spent time to be sure it is the case, so that it is clearer for you helping me. This is because my entire problem is Minimize A + B s.t. (1) and (2) Where B and (2) are in the post and A and (1) are hidden but can be optimized independently of B and (2) :) $\endgroup$
    – JKHA
    Oct 12 at 14:36
  • $\begingroup$ @Kuifje, oh, you meant, the graph theory problem? $\endgroup$
    – JKHA
    Oct 12 at 14:42
4
$\begingroup$

Try adding valid constraints $$ y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for $(i,j)$ such that $\hat{y}_i = 0$ and $j \in \tilde{V}\setminus\{i\}$} $$ that enforce the logical implications $$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k}$$

$\endgroup$
0

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.