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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ what advantages I have if conflict constraints are replaced with the clique constraints? Would you please explain it in details. $\endgroup$
    – KGM
    Jan 7, 2020 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, 2020 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$
    – KGM
    Jan 16, 2020 at 11:08
  • $\begingroup$ I suspect your cliques are incorrect. How are you computing cliques from conflicts? $\endgroup$
    – RobPratt
    Jan 16, 2020 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$
    – KGM
    Jan 17, 2020 at 16:23
7
$\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} $$

Improve this answer
$\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$
    – KGM
    Dec 17, 2019 at 22:48
  • $\begingroup$ please provide me a complete answer so that I can put the LP1 in a solver and solve it. $\endgroup$
    – KGM
    Dec 17, 2019 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$
    – Alexandre Frias
    Dec 18, 2019 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$
    – Alexandre Frias
    Dec 18, 2019 at 15:31
  • $\begingroup$ would you please recommend me a solver for BLP1. $\endgroup$
    – KGM
    Jan 7, 2020 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.