MATLAB Answers

Can this problem be expressed as a MILP problem?

3 views (last 30 days)
Giannis Zavos
Giannis Zavos on 27 Aug 2020
Edited: Giannis Zavos on 27 Aug 2020
This question was flagged by Bruno Luong
Hello community,
I was wondering whether the following problem can be expressed as a mixed integer linear programming (MILP) problem. I am new to this field.
The objective function is in parenthesis including the square (minimize the difference of the sum in brackets from the constant M).
i = 1,2,...N
c is my decision variable vector (should take values of either 0 or 1)
x, R, and M are knowns
E is a function of x
I is a function of V
The tricky part is that V is also equal to E(x)+R*I(V) and has one unique value
Also, E and I are functions given through data interpolation without real mathematical expression.
The outputs should be c, E, I, V (the last two have one value each, the first two should be vectors)
Could this be solved as a MILP problem through MATLAB?
I have solved this problem in two different ways, but it is interesting to see if there could be a more effective/fast method (such as MILP) that is easily expandable once implemented.
Thanks in advance,
Giannis
Edit:

  0 Comments

Sign in to comment.

Answers (1)

Bruno Luong
Bruno Luong on 27 Aug 2020
Edited: Bruno Luong on 27 Aug 2020
"The tricky part is that V is also equal to E(x)+R*I(V) and has one unique value."
Can we then assume this value is V(i) and known for any i? For any i solve it independently and put in an array.
If yes then your problem is simply find a combinations draw from V(1:N) such as the sum is closest to M.
This can be solve, yes as MILP, dynamic programming, etc...

  3 Comments

Giannis Zavos
Giannis Zavos on 27 Aug 2020
Hi Bruno,
Thank you for the suggestion.
All that is known for V is the range it can be in.
Also, that V is almost equal to sum of c*E(x), or in other words the term R*I(V) significantly smaller than E(x).
I don't think we can assume it as known, because it does not have values than can be calculated for each i. Its values are related to the whole expresion shown below (for which the combinations are 2^N because of c = 0/1, so too many to calculate).
Note, this is the correct expression for V, I did not define it properly in my question. Sorry if that caused any confusion.
Another way to solve it more easily would be to completly ingnore R*I and solve the following. Then calculate the V.
But that defeats the purpose of a "one-shot" accurate solution and brings me back to my previous implementaton that included a "while" loop to calculate the sum until it reaches M.
Bruno Luong
Bruno Luong on 27 Aug 2020
"Note, this is the correct expression for V, I did not define it properly in my question. Sorry if that caused any confusion. "
Oh yeah you should be.
Ahd your second definition does not make sense to me either. ci is not defined BEFORE you solve the minimum so what is it? You cannot define an objective function that depends on the solution ! That is absurbe.
And then you remove entirely Ri*I(V) in the cost function, fine why not. But then the problem becomes almost ike what I wrote earlier and can be trivial solved:
simply find a combinations draw from E(1:N) := E(xi) such as the sum is closest to M.
Al that to me that either
  1. I don't understand what you want
  2. You don't understand what you want
I'll flag this question unclear, sorry
Giannis Zavos
Giannis Zavos on 27 Aug 2020
"And then you remove entirely Ri*I(V) in the cost function, fine why not. But then the problem becomes almost ike what I wrote earlier and can be trivial solved:
simply find a combinations draw from E(1:N) := E(xi) such as the sum is closest to M."
Yes, please ignore that. I understand it is similar to what you said and all I was saying is that I had done that already.
As for the problem, maybe I was wrong from the begining that I though this was a MILP problem.
However, it is clear to me what I want to do:
I want to find howmany and which of the N numbers of Ei + Ri*I must be added to get closer to M. That will be expressed with c = 0 or 1. However, the problem is "looped" (but does have an optimum) as I is function of V = Ei +Ri*I (so function of itself in a way).
The simplest way I can write it, is
I want c, I, and V
I know Ei and Ri
the value of min is an output also (but I don't really care)
If this is not a MILP solvable problem, then that's all I need to know.
Thanks,
Giannis

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!