# Having an average constraint in a MI problem

 0 I have the following problem: $$\max xg$$ s.t. 1) $$\min(1,x/(x\mathbf{1}/y\mathbf{1}) > a$$ 2) $$x \leq yM$$ 3) $$x \geq ym$$ 4) $$x\mathbf{1} = 1$$ where $$x$$ is a $$1 \times n$$ vector with real numbers that we are trying to solve for, $$y$$ is a $$1 \times n$$ vector with binaries (unknown and to be solved simultaneously with x), $$a$$ and $$g$$ are $$1 \times n$$ vectors with with constant real numbers and $$\mathbf{1}$$ is a unit vector such that the expression $$x\mathbf{1}$$ represents the sum of all $$x$$s and $$(x\mathbf{1}/y\mathbf{1})$$ represents the average $$x$$. Is there any way I can linearize constraint 1) above (and especially the $$x/(x\mathbf{1}/y\mathbf{1})$$ expression?)? If yes, how? If no, any other ideas on how to solve such a problem? Thanks asked 09 Dec '13, 20:07 tatsi 1 accept rate: 0% fbahr ♦ 4.6k●7●16 Can you explain constraint 1? Particularly, how are you taking the min of two vectors...element-wise? (10 Dec '13, 00:20) Austin Buchanan yes. It will be element-wise. Thanks for taking a look at this. (10 Dec '13, 08:22) tatsi If that's the case, there's no need to take the min. For each i, if 1>a_i then the constraint is unnecessary. Otherwise, add the constraint x_i>a_i(x1/y1). You will also need to get rid of the strict inequality...use >= instead? (10 Dec '13, 10:46) Austin Buchanan

 2 I will first make some assumptions (correct me if any are wrong): I see that your question has been edited such that $$x 1$$ now reads $$x_1$$ however I think it is supposed to read $$x 1$$ as your notation here represents the sum of all the elements in the vector $$x$$, i.e. if we say that $$j$$ is the index then $$x 1=\sum_j x_j$$. Since most MIP-solvers do not support constraints using $$\gt$$ or $$\lt$$ I think constraint 1) should be $$\ge$$ instead of $$\gt$$. However if it is intentional that it should be $$\gt$$ then the usual way to circumvent this is to add some small value $$\epsilon \gt 0$$ to the right-hand-side of the constraint. Every element in $$a$$ is less than 1. Why do I assume that? Assume that $$a_j$$ is greater than 1 for some $$j$$. There are two cases for constraint 1) for index $$j$$; either case 1: $$\frac{x_j}{\frac{\sum_{j'}x_{j'}}{\sum_{j'}y_j}} \ge 1$$ or case 2: $$\frac{x_j}{\frac{\sum_{j'}x_{j'}}{\sum_{j'}y_j}} \lt 1$$. If it is case 1 then the left-hand-side of the constraint is 1 and since $$a_j$$ is greater than 1 then the constraint is violated so case 1 cannot occur. In case 2 the left-hand-side of constraint 1) is less than 1 and since the right-hand-side is greater than one then the constraint is violated. This means that if for any $$j$$ $$a_j \gt 1$$ the problem is infeasible so we can check for this before solving the model. Using assumption 3. we get that constraint 1) can be replaced by: $$\frac{x_j}{\frac{\sum_{j'}x_{j'}}{\sum_{j'}y_j}} \ge a_j$$ The reason for this is that the minimum of 1 and the expression here on the left-hand-side can only be one if the expression is greater than or equal one. From assumption 3 we know that the right-hand-side must be less than or equal one, so if the expression is greater than one then the constraint here holds and the minimum between this expression and 1 is will surely also be greater than $$a_j$$. Likewise if the expression is less than one then the minimum of one and this expression be the expression itself and so the constraint is valid. Now for the answer: Let's start with the expression $$\sum_j x_j / \sum_j y_j$$. Consider your constraint 4). Here you have restricted the elements in $$x$$ to sum to 1. This means that $$\sum_{j} x_{j} / \sum_{j} y_{j}=1/ \sum_{j} y_{j}$$ which eventually means that $$x_j / (\sum_{j'} x_{j'} / \sum_{j'} y_{j'}) = x_j / (1/ \sum_{j'} y_{j'}) = x_j \sum_{j'}y_{j'}$$ Now we just need to express the quadratic term $$x_jy_{j'}$$ for each pair $$(j,j')$$. I assume that non-negativity holds for all variables. For this we introduce the new variable $$z_{j,j'}=x_jy_{j'}$$. This is done by the following constraints $$z_{j,j'} \le My_{j'} \forall j,j'$$ $$z_{j,j'} \le x_j \forall j,j'$$ $$z_{j,j'} \ge x_j - M(1 - y_{j'}) \forall j,j'$$ Together with these constraints in the model constraint 1) can be replaced by the following $$\sum_{j'}z_{j,j'} \ge a_j \forall j$$ Now there may be some better/easier formulation, but that's just my quick and dirty solution. answered 10 Dec '13, 09:08 Niels-Christ... 71●4 accept rate: 0% Note that the expression $$z_{j,j'}=x_jy_{j'}$$ is not actually added to the model. The value of $$z_{j,j'}$$ is calculated by the three constraints I give right under the introduction of $$z_{j,j'}$$. (10 Dec '13, 09:33) Niels-Christ... > I see that your question has been edited such that $$x 1$$ now reads $$x_1$$ ... Yep, screwed this up - sorry for that. (10 Dec '13, 14:34) fbahr ♦ Thanks. This is very helpful. However, I kinda cheated when trying to simplify the problem. Let me restate: $$\max~ xg$$ s.t. 1) $$f(\mathbf{\min}(\vec{\mathbf{1}},\frac{\mathbf{x}}{\frac{x\vec{1}}{y\vec{1}}})) \ge a$$ 2) $$\mathbf{x} \le \mathbf{y}M$$ 3) $$\mathbf{x} \ge \mathbf{y}m$$ 4) $$\mathbf{x} \vec{\mathbf{1}} = 1$$ 5) $$x_i \ge 0 ~~\forall ~i \in \{1,2,...,m\}$$ 6) $$x_i \le 0 ~~\forall ~i \in \{m+1,m+2,...,n\}$$ where as before: i) $$\mathbf{x}$$ is a 1×n vector with real numbers that we are trying to solve for, ii) $$\mathbf{y}$$ is a 1×n vector with binaries (unknown and to be solved simultaneously with $$\mathbf{x}$$), iii) $$\mathbf{a}$$ and $$\mathbf{g}$$ are 1×n vectors with with constant real numbers iv) $$\vec{\mathbf{1}}$$ is a unit vector such that the expression $$\mathbf{x}\vec{\mathbf{1}}$$ represents the sum of all $$\mathbf{x}$$s and $$\frac{x\vec{1}}{y\vec{1}}$$ represents the average $$\mathbf{x}$$ and v) $$f(\mathbf{r}) = \sum_{i=1}^n h(r_i)$$ with $h(r_i) \left\{ \begin{array}{rl} 0 & \text{if } r_i <0,\ \alpha_1r_i+b_1 &\text{if } l_1 \le r_i < u_1,\\ \alpha_2r_i+b_2 &\text{if } l_2 \le r_i \le u_2,\\ .. \\ \alpha_nr_i+b_n &\text{if } l_{n-1} \le r_i < u_n,\\ \beta &\text{if } r_i \geq u_n,\\ \end{array} \right.$ Thanks (11 Dec '13, 02:59) tatsi
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×231
×71