9

I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient transformation into an LP or heuristic solution?

$$ \begin{array}{ll} \text{maximize} & v \\ \text{subject to}& \forall m=1,\ldots,M: \sum_{n=1}^N z_{nm} \leq P \\ &\forall n=1,\ldots,N: s_n = \sum_{m=1}^M z_{nm}q_n \\ &\forall n=1,\ldots,N: v \leq \frac{1}{d_n}s_n\\ &\forall m=1,\ldots,M \,\forall (n_1, n_2)\in A \text{ where } A_{n_1 n_2}=1: z_{n_1m} + z_{n_2m} \leq 1\\ &\forall m=1,\ldots,M \,\forall n=1,\ldots,N: z_{nm} \in \{0,1\} \end{array} $$ For example, $M=200$ and $N=50$.

KGM
  • 2,265
  • 7
  • 23

2 Answers2

8

These conflict constraints can be replaced with clique constraints of the form $$\sum_{n\in C} z_{n,m}\le 1 \quad \text{for all $m$},$$ where each $C$ is a clique in the graph with nodes $1,\dots,N$ and edges determined by $A$.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • what advantages I have if conflict constraints are replaced with the clique constraints? Would you please explain it in details. – KGM Jan 07 '20 at 14:49
  • As a simple example, suppose you have conflict constraints $x_1+x_2\le1, x_1+x_3\le1$, and $x_2+x_3\le1$. Then $x=(1/2,1/2,1/2)$ is feasible. But the clique constraint $x_1+x_2+x_3\le1$ is tighter, and $x=(1/2,1/2,1/2)$ is not feasible. – RobPratt Jan 07 '20 at 15:55
  • I considered a small system with $N=12$, I mean 12 nodes. With clique constraint, the solver output is 0 (the optimal solution), but when I used the conflict constraint I got the expected results. Why is that? – KGM Jan 16 '20 at 11:08
  • I suspect your cliques are incorrect. How are you computing cliques from conflicts? – RobPratt Jan 16 '20 at 13:28
  • I compute the maximal cliques from the adjacency graph of the nodes using Mathematica. Command: FindClique[AdjacencyGraph@A, Infinity, All] – KGM Jan 17 '20 at 16:23
  • OK, as a next step, I recommend checking your A matrix. – RobPratt Jan 17 '20 at 16:50
7

To transform an MILP into LP, you need to use an exponential number of variables:

Check the book: Optimization over Integers, by Bertsimas and Weismantel. Chapter 4 contains different ways to convert binary linear programming (BLP) into linear programming (LP).

The first step: $$s_n=\sum_{m=1}^{M} z_{n,m}q_{n}=q_{n}\sum_{m=1}^{M} z_{n,m}$$ bacause the summation is not over the index $n$. Thus, its constraint is $$v\leq \frac{s_n}{d_n}\implies v\leq \frac{q_n}{d_n}\sum_{m=1}^{M} z_{n,m}.$$

Second step: the problem can be converted into a binary program. I will remove its variable $v$ by fixing the order on $\dfrac{q_n}{d_n}\sum\limits_{m=1}^{M} z_{n,m} , \quad \forall n\in 1,\dots,N$.

$$\frac{q_n}{d_n}\sum_{m=1}^{M} z_{n,m} - \frac{q_{n-1}}{d_{n-1}}\sum_{m=1}^{M} z_{n-1,m} \geq 0 , \quad \forall n\in 2,\dots,N$$

After that, $v=\dfrac{q_1}{d_1}\sum\limits_{m=1}^{M} z_{1,m}$. The equivalent binary programming problem is

$$\begin{array}{ll} \max & \frac{q_1}{d_1}\sum_{m=1}^{M} z_{1,m} \\ \text{s.t.} & \sum\limits_{n=1}^{N} z_{n,m} \leq P, \quad \forall m\in 1,\dots,M\\ & \dfrac{q_n}{d_n}\sum\limits_{m=1}^{M} z_{n,m} - \frac{q_{n-1}}{d_{n-1}}\sum\limits_{m=1}^{M} z_{n-1,m} \geq 0 , \quad \forall n\in 2,\dots,N\\ & z_{n_1, m}+z_{n_2, m} \leq 1, \quad \forall (n_1, n_2)\in 1,\dots,N, \, \forall m\in1,\dots,M\\ & z_{n,m}\in\{0,1\}, \quad \forall n\in 1,\dots,N, \, \forall m\in 1,\dots,M \end{array}$$

OBS: Also, use the recommendation of Rob Pratt.

Final step:

Apply the same method shown in the book, where it is proved that the optimal objective value of LP1 is equal to BLP1 and the solution $w_S=1$ is $x_i=1, \forall i\in S$ and $x_i=0, \forall i\notin S$.

BLP1: $$ \begin{array}{ll} \max & cx\\ \text{s.t.} & Ax=b\\ & x\in\{0,1\} \end{array} $$ LP1: $$ \begin{array}{ll} \max & \sum\limits_{S\subseteq N}\left(\sum\limits_{i\in S} c_i\right)w_S\\ \text{s.t.} & (A_S -b)w_S =0,\quad \forall S\subseteq N\\ & \sum\limits_{S\subseteq N} w_S=1\\ & w_S \geq 0. \end{array} $$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Alexandre Frias
  • 676
  • 4
  • 7
  • Thank you very much for your answer. Unfortunately, I do not have access to the book you mentioned. Would you please elaborate on the final step and provide me the final formulation of my LP. I really appreciate your answer. – KGM Dec 17 '19 at 22:48
  • please provide me a complete answer so that I can put the LP1 in a solver and solve it. – KGM Dec 17 '19 at 23:01
  • The book contains a simple proof about the relation between these two problems LP1 and BLP1. You can rewrite the model presented in my answer in the matricial form. Then use the same formula shown to convert it into a linear programming problem. – Alexandre Frias Dec 18 '19 at 02:29
  • This LP1 has an exponential number of variables. For coding this model you need to learn how to generate a column in each step of simplex. I recommend you to use a solver in BLP1 and try to use a kind of column generation method. – Alexandre Frias Dec 18 '19 at 15:31
  • would you please recommend me a solver for BLP1. – KGM Jan 07 '20 at 15:07
  • To solve BLP1 you can use any commercial or open solver. I recommend you CBC Coin-OR: https://projects.coin-or.org/Cbc and JuMP as an interface. – Alexandre Frias Jan 07 '20 at 17:06
  • Unfortunately, the formulation you proposed based on ordering is not working! I think it is not correct. – KGM Jan 08 '20 at 15:53
  • why: $\dfrac{q_n}{d_n}\sum\limits_{m=1}^{M} z_{n,m} - \frac{q_{n-1}}{d_{n-1}}\sum\limits_{m=1}^{M} z_{n-1,m} \geq 0 , \quad \forall n\in 2,\dots,N$. – KGM Jan 08 '20 at 16:14
  • Your formulation and mine are equivalent. Please, read the deduction again. $$ v\leq \frac{s_n}{d_n}\implies v\leq \frac{q_n}{d_n}\sum_{m=1}^{M} z_{n,m}, \quad\forall n $$ in this case, the variable $$v=\min_{n}{\frac{q_n}{d_n}\sum_{m=1}^{M} z_{n,m}}$$ – Alexandre Frias Jan 08 '20 at 17:37
  • with your deduction formulation, the last element $\frac{q_N}{d_N}\sum_{m=1}^{M}z_{N,m}$ will have the highest value all the times!! But its not true. – KGM Jan 08 '20 at 17:49
  • what is the advantage of this equivalent formulation (lets say if I use the step 2 formulation)? – KGM Jan 08 '20 at 17:52
  • Fewer variables, strictly binary programming... – Alexandre Frias Jan 08 '20 at 18:17
  • could you please answer my second last comment. I tried with your formulation, but it does not work? As I mentioned in earlier comment "with your deduction formulation, the last element $\frac{q_N}{d_N}\sum_{m=1}^Mz_{N,m}$ will have the highest value all the time!! which is not true". – KGM Jan 08 '20 at 22:43
  • Probably, I could not enforce an order due to the coefficients $\frac{q_n}{d_n}$ are indexing by $n$ and not $m$. You are sure. But, there is another way to convert this problem into a BP to use the LP1. Let $H=\max_{n}{M\frac{q_n}{d_n}}$, you can replace $v=\sum_{k=0}^{log_{2}(H)}2^{k}x_k$ where $x_k\in{0,1}$. – Alexandre Frias Jan 21 '20 at 19:22
  • you better update your answer. – KGM Jan 26 '20 at 15:03