Dear all experts

I have had a problem since many years ago, but I've never tried to find the solution, but now I need it urgently.

Many of friends and classmates would ask me if they could use "condition on variables" in a summation in GAMS. Obviously for me, it was not possible. But all the time my answer was one thing: you have a problem in your model building procedure, try to modify it, it is not standard to have condition on decision variable which its value is obtained through the interaction of parameters, sets, scalars and etc. In my idea, it was a blind loop when range of a summation is dependent on a decision variable! Now, my question is: am I in right side or not?

I really appreciate any kind of suggestion. Looking for your answers

Bests

asked 10 Sep '12, 11:45

Bob%20Pay's gravatar image

Bob Pay
7727
accept rate: 0%


If I'm understanding you correctly, you are asking if it is possible to write a conditional sum, with conditions on the variables instead of the counters, for instance, sum(xi if xi > 2). This is equivalent to the SUMIF function in Excel.

Is this right?

If so, yes, it is possible if you introduce binary variables (resulting in a Mixed-Integer Program).

For the above example, i.e. \(y = \sum_{i=1}^{n} x_i\) with the condition that we only sum terms that obey the predicate \(x_i > 2\), we can state the problem as follows:

$$ \begin{align} &y = \sum_{i=1}^{n} w_i\\ &w_i = \left\{ \begin{array}{ll} x_i, & x_i > 2\\ 0, & x_i \leq 2 \end{array} \right. \end{align} $$

If you're solving a Mixed Integer Nonlinear Program, you can write your formulation as follows (assuming that \(x_i\) has the following bounds \(L \leq x_i \leq U\):

$$ \begin{align} &y = \sum_{i=1}^{n} \delta_i x_i\\ & \delta_i \in \{0,1\}\\ & (1-\delta_i)L + (2+ \epsilon)\delta_i \leq x_i \leq \delta_i U + 2(1 - \delta_i) \end{align} $$

If you want to further reduce that to a Mixed-Integer Linear Program (linearizing the bilinear constraint at the expense of introducing more binary variables):

$$ \begin{align} &y = \sum_{i=1}^{n} z_i\\ & \delta_i \in \{0,1\}, y_i \in \{0,1\}\\ & (1-\delta_i)L + (2+ \epsilon)\delta_i \leq x_i \leq \delta_i U + 2(1 - \delta_i)\\ & Ly_i \leq z_i \leq Uy_i\\ & L(1-y_i) \leq x_i - z_i \leq U(1-y_i) \end{align} $$

(The linearization was done by applying the trick in Section 2.8 of the FICO MIP guide.)

Another interpretation

Marco alerted me to another interpretation: suppose \(y = \sum_{i=1}^{n} x_i\) where \(n \in \{2,3,\ldots, 7\}\) is a variable (!). There is a way to handle this, but it can get expensive if the domain of \(n\) is large. We can write:

$$ \begin{align} &y = \sum_{i=1}^{7} \delta_i x_i\\ & \delta_7 \leq \delta_6 \leq \delta_5 \leq \ldots \leq \delta_2\\ & \delta_1 = 1 \end{align} $$

I remember there being a question some time ago about optimization problems over \(\mathbb{R}^n\) where \(n\) is a variable. The above is one of the ways to handle it (but again, it is awfully expensive when the domain of \(n\) is large, especially if linearizations are desired). I would say this is one of those "last resort" type approaches -- in general it's not a good idea to specify optimization problems with decision variable vectors of variable dimension.

link

answered 10 Sep '12, 12:26

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 10 Sep '12, 14:08

Dear Gilead yes, you got my question. and according to your answer, I think i am in a right side!

Thank you.

(10 Sep '12, 12:30) Bob Pay

I really hope I've understood your question correctly; if so, then it would seem that it is possible to do this (in fact, the formulation I've stated above is a fairly standard one). The disadvantage is that these types of conditions are by nature fairly computationally expensive to implement in a mathematical program.

(10 Sep '12, 13:06) Gilead ♦

I understood the question as in: \(\sum_{i=1}^x y_i\) where \(x\) and \(y_i\) are variables.

(10 Sep '12, 13:13) Marco Luebbecke ♦

@Marco: Ah! That puts quite a different complexion on the issue then. However, I'm thinking if the x in your expression has an integral value with a fairly small feasible domain (say, x=2,3,..7), it is still possible to represent it by pre-specifying it as a bounded integer variable, and writing an MIP formulation for it. It's hugely expensively, ill-advised, but possible.

(10 Sep '12, 13:19) Gilead ♦

I think both can happen, but the one, Marco mentioned, was more near to my intention.

The point that Gilead indicated, is another possibility and fortunately has solution.

But I wanted to emphasize more on the model building. Because as you mentioned Gilead: both are not advised. Your solution was very new for me, and I have not seen it before, for this, I am really thankful.

(11 Sep '12, 02:40) Bob Pay
1

Oops... accidentally deleted my comment. Anyway, the main point is that what you asked for is: 1) not directly possible. 2) but is possible through indirect means, but you pay a huge computational price for it. (Marco's answer also alludes to this--and I agree). That's my 2 cents worth.

(11 Sep '12, 12:18) Gilead ♦
showing 5 of 6 show 1 more comments

I will dissent a bit from the other answers. As they note, doing it directly in a mathematical programming model is not possible, although in some cases there is a work-around if you are willing to add binary variables and/or constraints. More precisely, it is not possible for a typical MP solver to handle it. (You can certainly write conditional summations in algebra; just not in most MP languages.)

It is both possible and common, however, to have summations that depend on the states of variables in a constraint program. CP languages allow, CP solvers can deal with it.

I don't know about GAMS, but some modeling languages (OPL comes to mind) are intended to support both MP and CP, and so will allow the sort of thing you have in mind (possibly conditional on your designating the model a CP).

link

answered 10 Sep '12, 18:29

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Good point about CP! Now it's just a matter of phrasing, but I'm wondering... even though it may be inconvenient and expensive to write conditional sums inside an MP, wouldn't it be fair to say--within broad interpretations of the term--that it is "possible" within the limitations of an an MIP framework? ;-) There may not be a built-in GAMS keyword for a conditional sum, but it is still in a sense representable. Or maybe it's just me: whenever I see an IF or some other disjunction, my brain automatically translates it into a binary formulation. ;-)

(10 Sep '12, 19:02) Gilead ♦

Sorry, I'm just being pedantic here... ;-) I do agree with you. When I first learned to write proper MPs, I was appalled that I couldn't use IF statements in my model. (I had been using IF's in my MATLAB models, optimized using Optimization Toolbox, and it seemed to work fine before... for small models....)

(10 Sep '12, 19:10) Gilead ♦

"doing it directly in a mathematical programming model is not possible" it was exactly what I wanted to know.

(11 Sep '12, 02:49) Bob Pay

You know Gilead (you look expert and i learned good point form you), most make this mistakes. When they are modeling at first, they have so many preoccupation of general programming. But I always think to myself, It's better to think MPly (new adverb!) in process of building models and just forget the existence of any software.

(11 Sep '12, 02:53) Bob Pay
2

@Gilead: Actually, you can now use "if" statements in some modeling languages (AMPL comes to mind) if you are using a solver that supports them (CPLEX comes to mind). CPLEX refers to them as "indicator constraints". There are, however, some limitations. I frequently see someone trying to write "if x > 0 then ..." or "if ... then x > 0", and the strict inequality still requires fudging.

There's also a distinction between "can be done" and "is practical to do". \(\sum_{i=1}^y x_i\) with \(y\in\{1,\dots,10000\}\) makes for a rather chubby model.

(11 Sep '12, 09:37) Paul Rubin ♦♦

Oh that's interesting, I didn't know AMPL did that. Yes! That's exactly the nuance I was trying to convey... it "can be done", but umm, does one really want to... Your point about CPs is an excellent one; I need to revisit them. MIPs do start to get unwieldy when there are too many logical conditions involving bilinear terms that have to be linearized...

(11 Sep '12, 11:59) Gilead ♦

@Paul Rubin: In your answer you talked about OPL and it triggered my curiosity to find more (I haven't heard about it before). I have downloaded the user guide, but I don't know how to download the software. Is there any demo version for student? and one more thing, is it within the IBM Cplex or not?

(11 Sep '12, 16:00) Bob Pay
1

@Bob Pay: The IBM "CPLEX Studio" bundle contains CPLEX, CP Optimizer (the solver for CPs), and OPL IDE (an IDE for OPL models using either or both solvers). I don't think there is a student version, but faculty can join the IBM Academic Iniative (free) and then download it at no charge. I believe the license allows them to distriburte copies to students.

The home for the academic initiative is www <dot> ibm <dot> com <slash> developerworks <slash> university <slash> academicinitiative <slash> index <dot> html.

(11 Sep '12, 16:14) Paul Rubin ♦♦
showing 5 of 8 show 3 more comments

What you are looking for would be highly appreciated, but this is not possible in mathematical programming (given, I understand you right). You may consider variables with a different meaning. As a very rough example, in scheduling you may wish to have variables expressing the start time of a job. Summation may depend on the value of the start time (for whatever reason, maybe for a capacity constraint). An alternative is to model with binary variables, for every possible point in time a different variable to state whether the job starts or not. There, the variable value (of the first model's variables) "somehow" goes into the summation.

So: you are on the right side!

link

answered 10 Sep '12, 12:10

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

1

I really appreciate your comments and that you agree of my being in right side, dear Marco Luebbecke.

Your example was really insightful. Most of the time the problem is solved by ,as you said, "consider variables with a different meaning".

I am really thankful.

(10 Sep '12, 12:25) Bob Pay

Generally, I think the answer is "Yes, you're right". But it might depend on your approach to solve the problem. If you intend to solve the model via an artificial intelligence method such as a metaheuristic, I don't think such declarations would be wrong. In fact, a metaheuristic could easily handle all these conditions via its encoding and decoding mechanisms. You must note that in this situation, your mathematical model is merely acting as a tool for better understanding the problem and nothing more.

However if you want to solve your problem via mathematical programming methods, the answer is no. All the mathematical programming solution methods require a complete representation of your problem (e.g. in case of MIP and LP model, solvers require a matrix representation of the problem structure).

Personally, I think it would be for the best not to define such conditions so that you could compare your solutions obtained from metaheuristics with exact solutions from solvers.

link

answered 10 Sep '12, 12:11

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 10 Sep '12, 12:13

Dear Ehsan, I agree with you about meta heuristic and other computational intelligence methods. But as you mentioned above, I am more concerned about exact algorithms that need clear and complete presentation of mode.

Thank you really.

(10 Sep '12, 12:27) Bob Pay
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:

×51
×4
×2
×2
×2

Asked: 10 Sep '12, 11:45

Seen: 4,665 times

Last updated: 11 Sep '12, 16:17

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