3
$\begingroup$

I have a problem with inequality constraint. And I'm going to merge the constraints.I know that we can add surplus and slack variables in order to achieve equality constraints. And then use below method.

I know Merge constraints for equal constraints ,And I'll explain it further. my trouble is i have more than two constraint .

my problem
\begin{equation} \begin{split} \min &\; \sum_{i=1}^N \sum_{k=1}^K \sum_{l=1}^L b_{kl} Y_{ik}Y_{il}+\sum_{i=1}^N\sum_{j=1}^M c_{i,j} X_{i,j}\\ \text{s.t.} & \; \sum_{i=1}^N X_{ij} =1 ,\ \ j=1.2,...,M \\ & \; a_i Z_i \le \sum_{j=1}^M X_{ij} \le b_i Z_i ,\ \ i=1.2,...,N\\ & \;p_i Z_i \le \sum_{k=1}^K Y_{i,k} \le q_i Z_i ,\ \ i=1.2,...,N\\ &\; X_{ij} \le Y_{ik} ,\ \ i=1.2,...,N , \ \ j=1.2,...,M , j\in t_k \\ &\; Y_{ik} \le \sum _{j \in J} X_{i,j} ,\ \ i=1.2,...,N , \ \ K=1.2,...,k \\ &\; X_{ij} \in \{0,1\} \ \ j=1.2,...,M , i=1,...,N\\ &\; Z_{i} \in \{0,1\} \ \ i=1,...,N\\ &\; Y_{ik} \in \{0,1\} \ \ K=1.2,...,k , i=1,...,N\\ \end{split} \label{OP9} \end{equation}

where i,j,k is set, i=1,..,32 Represents the number of classes, j=1,..,512 Represents the number of student, k=1,..,40 Represents the type of student. $t_k$ is subset of $j$. Which indicates student jth belongs to which type. for example , if we consider type k=1, then all student with type ′1′ are t1={2,10,78,69,114,500}.

$c_{ij} ,b_{k,l} ,a_i,b_i,p_i,q_i $ are parameter.

i want to use below method , To merge these constraints :

$a_i Z_i \le \sum_{j=1}^M X_{ij} \le b_i Z_i ,\ \ i=1.2,...,N$

or this

$p_i Z_i \le \sum_{k=1}^K Y_{i,k} \le q_i Z_i ,\ \ i=1.2,...,N$ .

How can I use below method for more than two constraints?


****method for merge****

i know merging constraint for equality as below : suppose we have two integer constrain in bounded variable

\begin{equation} \begin{split} \max &\; p_j x_j\\ \text{s.t.} & \; \sum_{j=1}^n w_{1j} x_j =c_1\\ & \;\sum_{j=1}^n w_{2j} x_j =c_2\\ & \; 0\le x_j\le u_j , &\; x_j , \text integer , j=1.2,...,n \end{split} \label{OP} \end{equation}

let

\begin{equation} \begin{split} \\ g(x)=c_1-\sum_{j=1}^n w_{1j} x_j\\ & \; \ \\ h(x) = c_2-\sum_{j=1}^n w_{2j} x_j \\ & \; \end{split} \label{OP1} \end{equation} by using bounds on $x_j$ we derive the following bound on $g(x)$ :

\begin{equation} \begin{split} \\ c_1-\sum_{j=1}^n w_{1j}^+ x_j \le g(x) \le c_1-\sum_{j=1}^n w_{1j}^- x_j\\ & \; \end{split} \label{OP3} \end{equation}

where $w_{1j}^+ = \max \{0,w_{ij}\}$ and $w_{1j}^- = \min \{0,w_{ij}\}$

if we choose a positive integer $\lambda$ satiating :

$\lambda > max \{ c_1-\sum_{j=1}^n w_{1j}^- u_{j}, c_1-\sum_{j=1}^n w_{1j}^+ u_{j} \}$

then we have $|g(x)| < \lambda$

now multiply the constrain $\sum_{j=1}^n w_{2j} x_j =c_2$ by $\lambda$ and it to the first constrain $\sum_{j=1}^n w_{1j} x_j =c_1$ boating the following :

\begin{equation} \begin{split} \max &\; p_j x_j\\ \text{s.t.} & \; \sum_{j=1}^n (w_{1j} + \lambda w_{2j} )x_j =c_1 +\lambda c_2\\ \\ & \; 0\le x_j\le u_j , &\; x_j , \text integer , j=1.2,...,n \end{split} \label{OP5} \end{equation}

It's proven that if the $\lambda$ is chosen like the above, the two problem are same.

$\endgroup$
  • 1
    $\begingroup$ Why do you have the urge to merge? $\endgroup$ – Mark L. Stone Jun 24 '18 at 12:55
  • 2
    $\begingroup$ @Mark L. Stone hello I want to know if the constraints are combined ، and we use Lagrangian relaxation , The obtained boundary differs from case that constraints are not combined ? $\endgroup$ – linkho Jun 24 '18 at 14:17
  • $\begingroup$ @linkhochon do you want to merge constraint till you have only one constraints? $\endgroup$ – ken kavaza Jun 24 '18 at 17:13
  • $\begingroup$ @ken kavaza hello , no I don't want to have only one constraints , but I want to merge some constraints , for example I want to merge $ p_i Z_i \le \sum_{k=1}^K Y_{i,k} \le q_i Z_i ,\ \ i=1.2,...,N$ $\endgroup$ – linkho Jun 24 '18 at 17:21
  • $\begingroup$ Is your Lagrangian relaxation even solvable? Would you like to merge those $N$ double-sided inequalities into a single one? $\endgroup$ – LinAlg Jun 27 '18 at 14:17
1
+100
$\begingroup$

Take $p_i Z_i \leq \sum_{k=1}^K Y_{i,k} \leq q_i Z_i$, which is equivalent to: $$\sum_{k=1}^K Y_{i,k} - s_{i} - p_i Z_i = 0, \quad \sum_{k=1}^K Y_{i,k} + t_{i} - q_i Z_i = 0$$ The slack variables $s_i$ and $t_i$ are integer and range between 0 and $K$. Let me focus on the first constraint. The absolute value of the left hand side is bounded by $2K$, so you can use any $\lambda_2>2K$ in your method to merge the constraints for $i=1$ and $i=2$: $$ \begin{align} \left( \sum_{k=1}^K Y_{1,k} - s_{1} - p_1 Z_1 \right) + \lambda_2 \left( \sum_{k=1}^K Y_{2,k} - s_{2} - p_2 Z_2 \right) = 0. \end{align}$$ The left hand side is bounded in absolute values by $(1+\lambda_2)2K$, so you can use your method to combine the constraint above with the constraint for $i=3$ using any $\lambda_3 > (1+\lambda_2)2K$: $$ \begin{align} & \left( \sum_{k=1}^K Y_{1,k} - s_{1} - p_1 Z_1 \right) + \lambda_2 \left( \sum_{k=1}^K Y_{2,k} - s_{2} - p_2 Z_2 \right) + \lambda_3 \left( \sum_{k=1}^K Y_{3,k} - s_{3} - p_3 Z_3 \right)= 0. \end{align}$$ Now take $\lambda_4 > (1+\lambda_2+\lambda_3)2K$ to continue the pattern.

$\endgroup$
  • 1
    $\begingroup$ @LinAlg why the range of slack variable is between 0 and K , how you receive to K , please explain. Thanks $\endgroup$ – ken kavaza Jun 27 '18 at 17:45
  • 1
    $\begingroup$ @kenkavaza looking at $p_i Z_i \leq \sum_{k=1}^K Y_{i,k}$, the left hand side is at least zero while the right hand side is at most $K$, so the difference is at most $K$. $\endgroup$ – LinAlg Jun 27 '18 at 18:18
  • $\begingroup$ @linkhochon That is true; I have updated my answer. $\endgroup$ – LinAlg Jun 27 '18 at 18:24
  • 1
    $\begingroup$ @LinAlg i think it is not true. because in question says $K=1,...,40$ so in the summation $\sum _{k=1}^K Y_{i,k} $ The maximum amount it takes can be 40. but if we have $z_i=1$ and suppose for example we have $p_i =120$ then term $p_i Z_i$ is equal to 120 . and then the difference is 88 ,and so the difference is not at most K, is it true ? I mean that the slack values depend on the parameters $p_i$ $\endgroup$ – ken kavaza Jun 28 '18 at 4:18
  • 1
    $\begingroup$ @kenkavaza it is true as long as $p_i \geq 0$; in your example the difference is -88 instead of 88, and -88 is not allowed because the slack variable has to be nonnegative $\endgroup$ – LinAlg Jun 28 '18 at 11:52

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.