$\begingroup$
$\endgroup$
5
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?
-
$\begingroup$ Brute force over the possibilities for which inputs are maximal. $\endgroup$user12859– user128592016年02月25日 10:45:42 +00:00Commented Feb 25, 2016 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.– D.W. ♦2016年02月25日 12:00:02 +00:00Commented Feb 25, 2016 at 12:00
-
$\begingroup$ What is it now, an LP or IP? $\endgroup$Raphael– Raphael2016年02月25日 15:25:49 +00:00Commented Feb 25, 2016 at 15:25
-
$\begingroup$ @ Raphael..it is LP but values of decision variables can be binary only. $\endgroup$Abhay– Abhay2016年02月28日 06:59:09 +00:00Commented Feb 28, 2016 at 6:59
-
1$\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.– D.W. ♦2016年02月29日 00:19:39 +00:00Commented Feb 29, 2016 at 0:19
1 Answer 1
$\begingroup$
$\endgroup$
5
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$.
answered Feb 25, 2016 at 12:02
-
$\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– Abhay2016年02月28日 06:56:04 +00:00Commented Feb 28, 2016 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– Abhay2016年03月01日 04:13:29 +00:00Commented Mar 1, 2016 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– Christian2018年03月22日 20:25:38 +00:00Commented Mar 22, 2018 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$2018年03月22日 21:08:25 +00:00Commented Mar 22, 2018 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– Christian2018年03月23日 21:53:46 +00:00Commented Mar 23, 2018 at 21:53
Explore related questions
See similar questions with these tags.