8
$\begingroup$

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$.

$\endgroup$
8
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ what advantages I have if conflict constraints are replaced with the clique constraints? Would you please explain it in details. $\endgroup$ Jan 7 '20 at 14:49
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jan 7 '20 at 15:55
  • $\begingroup$ 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? $\endgroup$ Jan 16 '20 at 11:08
  • $\begingroup$ I suspect your cliques are incorrect. How are you computing cliques from conflicts? $\endgroup$
    – RobPratt
    Jan 16 '20 at 13:28
  • $\begingroup$ I compute the maximal cliques from the adjacency graph of the nodes using Mathematica. Command: FindClique[AdjacencyGraph@A, Infinity, All] $\endgroup$ Jan 17 '20 at 16:23
6
$\begingroup$

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} $$

$\endgroup$
15
  • $\begingroup$ 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. $\endgroup$ Dec 17 '19 at 22:48
  • $\begingroup$ please provide me a complete answer so that I can put the LP1 in a solver and solve it. $\endgroup$ Dec 17 '19 at 23:01
  • $\begingroup$ 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. $\endgroup$ Dec 18 '19 at 2:29
  • $\begingroup$ 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. $\endgroup$ Dec 18 '19 at 15:31
  • $\begingroup$ would you please recommend me a solver for BLP1. $\endgroup$ Jan 7 '20 at 15:07

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.