1
$\begingroup$

I have liner programme with set of $x_{3n}$ variables where $x_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve.

Using these variables, I want to form following constraint :

$max(x_1 , x_2.., x_n) + max(x_{n+1} , x_{n+2}.. , x_{2n}) + max(x_{2n+1} , x_{2n+2}..., x_{3n}) >= q$

Constraint is : Sum of max variable in set of variables should be greater than q.

How can I write constraint using $max$ operation in LP Solve?

$\endgroup$
  • $\begingroup$ Brute force over the possibilities for which inputs are maximal. ​ ​ $\endgroup$ – user12859 Feb 25 '16 at 10:45
  • $\begingroup$ Max over 0/1 variables is the same as logical OR. See cs.stackexchange.com/q/12102/755 for some techniques you can try. $\endgroup$ – D.W. Feb 25 '16 at 12:00
  • $\begingroup$ What is it now, an LP or IP? $\endgroup$ – Raphael Feb 25 '16 at 15:25
  • $\begingroup$ @ Raphael..it is LP but values of decision variables can be binary only. $\endgroup$ – Abhay Feb 28 '16 at 6:59
  • $\begingroup$ It's not LP if the variables are restricted to be binary or integers. That's called ILP (integer linear programming). $\endgroup$ – D.W. Feb 29 '16 at 0:19
1
$\begingroup$

Introduce variables $m_1,m_2,m_3$ to represent the three maxes.

Add the linear inequality $m_1 + m_2 + m_3 \ge q$.

Then, add the following extra inequalities for $m_1$:

  • $0 \le m_1 \le 1$
  • $m_1 \le x_1 + x_2 + \dots + x_n$
  • $x_1 \le m_1$, $x_2 \le m_1$, $\dots$, $x_n \le m_1$

and similarly for $m_2$ and $m_3$.

$\endgroup$
  • $\begingroup$ @ D.W. thanks ..it's working :). Previously I followed the second answer given in the link you shared but it was taking too much time to solve the problem. $\endgroup$ – Abhay Feb 28 '16 at 6:56
  • $\begingroup$ ,I did, but to show and display it publicly I have to earn 15 reputations :(. I will definitely do once I earn 15 reputations. $\endgroup$ – Abhay Mar 1 '16 at 4:13
  • $\begingroup$ @D.W. I understand the necessity for the final bullet point and was able to come up with it independently, but could you explain the reason for the other two? It seems the other two would happen implicitly due to constraints on x_i. $\endgroup$ – Christian Mar 22 '18 at 20:25
  • $\begingroup$ @Christian, the first is necessary, otherwise we might find a solution where $m_1$ is bigger than 1 (which won't be the max of $x_1,\dots,x_n$). The second is necessary, otherwise we might have $x_1=\cdots=x_n=0$ but $m_1=1$ (which wouldn't be the max). $\endgroup$ – D.W. Mar 22 '18 at 21:08
  • $\begingroup$ @D.W. Thanks for clarifying. I was thinking through the lens of a minimization problem where those things would be impossible and hadn't considered the more general case. $\endgroup$ – Christian Mar 23 '18 at 21:53

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.