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's gravatar image

tatsi
1
accept rate: 0%

edited 11 Dec '13, 08:09

fbahr's gravatar image

fbahr ♦
4.6k716

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

I will first make some assumptions (correct me if any are wrong):

  1. 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\).
  2. 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.
  3. 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.
  4. 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.

link

answered 10 Dec '13, 09:08

Niels-Christian%20F%20Bagger's gravatar image

Niels-Christ...
714
accept rate: 0%

edited 10 Dec '13, 09:31

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 09 Dec '13, 20:07

Seen: 827 times

Last updated: 11 Dec '13, 08:15

OR-Exchange! Your site for questions, answers, and announcements about operations research.