Hello all I want to convert following conditions to MILP model. Actually, the value of a variable (y) is determined as follows. can anyone help me?

y=alpha(1) if x < x(1); y=alpha(2) if x(1)<= x <x(2); y="alpha(3)" if="" x(2)<="x" <x(3);="" .="" .="" .="" y="alpha(n)" if="" x(n-1)<="x" <x(n);="" y="alpha(n+1)" if="" x="">= x(n);

, where alpha(i) is a constant and are nonincreasing. it is worthy to mention that these conditions are in objective function which should be minimized.

asked 29 Aug '16, 04:32

Amin-Sh's gravatar image

accept rate: 0%

edited 29 Aug '16, 06:45

The missing piece is to model \(z_i = 1 \iff x_{i-1} \le x \le x_i - \epsilon\). Assuming \(L \le x \le U\), you can do that as follows: \[x_{i-1} z_i + L(1-z_i) \le x \le (x_{i}-\epsilon) z_i + U(1-z_i).\]

Note that this formulation does not depend on \(\alpha_i\) nonincreasing.


answered 30 Aug '16, 10:23

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 30 Aug '16, 10:25

Thanks for your Help. Does this assumption that alpha(i) are nonincreasing help up to avoid using binary variables?

(01 Sep '16, 06:53) Amin-Sh

If \(\alpha_i = \alpha_{i+1}\), you can merge those two consecutive intervals and thus reduce the number of binary variables by one; repeat if possible. Unless your function is actually constant (all \(\alpha_i\) equal) and not just piecewise constant, it is nonconvex and cannot be modeled with pure LP.

Your original question mentions MILP, but if the \(z_i\) are the only integer variables, you can avoid them by instead solving \(n+1\) separate LPs. That approach is equivalent to branching on the constraint \(\sum_i z_i = 1\).

(01 Sep '16, 09:40) Rob Pratt

Actually, my model is an MIP model, but integer (binary) variables can be fixed through benders decomposition algorithm and subproblem is reduced to LP.

Is there any paper which applied this procedure ("you can avoid them by instead solving n+1n+1 separate LPs. That approach is equivalent to branching on the constraint ∑izi=1∑izi=1.")?


(05 Sep '16, 09:20) Amin-Sh

I don't have any reference to a paper. For the \(n+1\) LPs, I just mean to force \(x\) to be in the \(i\)th interval, and then the best of the resulting \(n+1\) solutions is optimal. This approach assumes that you really have only one such piecewise constant \(y\) to model.

(05 Sep '16, 13:07) Rob Pratt

Hints: introduce a binary variable \(z_i\) for each interval, with \(\sum_i z_i = 1\) and \(\sum_i \alpha_i z_i = y\).


answered 29 Aug '16, 13:31

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

Thanks but how I could specify that y=alpha(i) if the value of variable x is in the interval corresponding to the alpha(i)?

(30 Aug '16, 09:36) Amin-Sh
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 29 Aug '16, 04:32

Seen: 1,023 times

Last updated: 05 Sep '16, 13:07

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