Hey guys,

I'm having trouble figuring out a robust way to implement the idea of "sink" decision variables for my constraints. My post has rambled on a lot longer than I had planned, but the crux of it is that I am trying to figure out a clever way to choose an objective co-effiecent value for "sink" decision variables which are used to prevent infeasible solutions.

So for example, say I start off with the following problem (solved using this simple on-line solver):

\[ \begin{eqnarray} \min p = & 5x &+ 10y &+ 60z & \\ s.t.\quad\; &0.05x &+ 0.02y &+\; z &= 1 \\ & x,&\quad y,&\quad z &\le 1 \end{eqnarray} \]

Which returns: Optimal Solution: p = 60; x = 0, y = 0, z = 1. To give this example a bit more context, say my initial 0.05x + 0.02y + z = 1 constraint represents how £100 for investment is constrained across funds x, y and z, and their objective co-efficients represent a risk metric. So I want to minimise my risk while allocating as much of the £100 as possible across funds x, y and z. But it might not be possible to allocate all £100 to x, y, and z due other constraints like z <= 0.5 (i.e. only allocate a max of £50 to fund z). So it's the decision variables I'm after; I don't care about the final objective function value (as long as its the minimum of course!).

All good so far. But now say z <= 0.5 (these upper bound constraints are usually always 1, but I set it to 0.5 here to simulate a non-feasible situation that could occur due to many more complicated non-upper bound constraints). This would result in No optimal solution exists for this problem. i.e. non-feasible.

So I thought I could introduce the idea of a "sink" decision variable that essentially would prevent the problem from being infeasible, but only as a last resort (i.e. assign to the "sink" decision variable that has an appropriatly high objective co-effecient as to make it always the most expensive).

So our example would look like:

\[ \begin{eqnarray} \min p = & 5x &+ 10y &+ 60z &+ 1000sink_1 & \\ s.t.\quad\; &0.05x &+ 0.02y &+\; z &+\; sink_1 &= 1 \\ & x,&\quad y,& &\quad sink_1 &\le 1\\ & & &\quad z & &\le 0.5 \end{eqnarray} \]

Which returns: Optimal Solution: p = 475; x = 1, y = 1, z = 0.5, sink1 = 0.43. So the sink1 decision variable would represent £43 that is left over in our above example (i.e. 0.43 => £43). If I re-wrote the constraint from 0.05x + 0.02y + z + sink1 = 1 to 0.05x + 0.02y + z <= 1, this would better reflect what I'm trying to achieve I think. The problem with this is that the optimiser will just set all the decision variables to zero!

The key here is that the objective co-effecient of the sink1 is high enough (i.e. greater than its tipping point) so that increasing its value towards positive infinity will not change the outcome. So if the value 100 was choosen instead of 1000 for the sink1 objective co-effecient like above, we would get the following result: Optimal Solution: p = 80; x = 0, y = 0, z = 0.5, sink1 = 0.5. In this case assigning to sink1 is better than assigning as much as possible to x, y and z first.

In our example, the "tipping" point happens when the objective co-effecient of sink1 goes from 500 to 501. So with a co-efficient of 501 or higher, the outcome will never change (i.e. x = 1, y = 1, z = 0.5, sink1 = 0.43).

So in our example, we introduce sink1 into the objective function and into the constraint. The tipping point for the constraint can be found by first dividing every decision variable's objective co-effecient by its constraint co-effecient, and taking the max value from these numbers, which gives a tipping point of 500 (i.e. MAX(5/0.05, 10/0.02, 60/1).

The fun (finally!) begins when I try to apply this to a problem with two non-upper bound constraints which use two sink decision variables, such as one similar to our previous one above:

\[ \begin{eqnarray} \min p = &5x &+ 10y &+ 60z &+ 501sink_1 &+ 501sink_2 & \\ s.t.\qquad &0.05x &+ 0.02y &+ z &+\; sink_1 & &= 1 \\ &0.5x &+ 0.02y &+ z & &+\; sink_2 &= 1 \\ &x, &\quad y, & &\quad sink_1, &\quad sink_2 &\le 1 \\ & & &\quad z & & &\le 0.5 \end{eqnarray} \]

Which returns: Optimal Solution: p = 260.45; x = 1, y = 0, z = 0.5, sink1 = 0.45, sink2 = 0. However, I discovered that the tipping point for sink1 is no longer ecutally 500, but 544, which I only found through to trial and error. Playing around with different constraint co-efficients, it seems to me my way of calculating the tipping point is sufficient in some cases but not in others, which is not good enough for what I want to do.

If you have made it this far I thank you! But if you think you know how I might be accurately able to determine the "tipping point" objective co-efficient for my sink variables like above and happen to live in London, I'll buy you a pint!

Cheers, Fionn


P.S. I'll brush up on my sensitivity analysis and try figure out if its what I'm after.

P.S.S. Ehsan was indeed correct, it's the sensitivity analysis around the allowable increase/decrease of the artificial (or "sink" as I called them) variables co-efficients that I am looking for.

So in my case, for each artificial variable that I introduce I want the allowable increase to be positive infinity.

It seems to me that I should assign an arbitrary large objective co-efficient for each artificial variable that I introduce to the problem, solve the problem, determine whether the allowable increase is positive infinity for each artificial variable, and if not, increase that artificial variables co-efficient by at least the allowable increase value (probably more), re-solve, and repeat until all the artificial variables allowable values are positive infinity.

Thanks again for all the help guys, much appreciated. If you're ever in London, the round is on me!

asked 31 May '12, 09:36

FionnMac's gravatar image

FionnMac
334
accept rate: 0%

edited 08 Jul '12, 16:47

fbahr's gravatar image

fbahr ♦
4.6k716

1

FYI, what you are doing is known as a penalty method, and what you call a "sink" is more properly known as an "artificial variable".

(31 May '12, 17:57) Paul Rubin ♦♦

What I understand from your question is that you're looking for the sensitivity analysis of your model for the sink1 coefficient. In LP, sensitivity analysis of a single objective function coefficient while keeping other coefficients unchanged results in a range for the desired objective function coefficient in which the optimal solution is unchanged. Most of modern solvers offer such analysis for linear programming models.

ps #1. Your second model with sink1 coefficient being 1000 results in p = 475, not 60. Also, sink1 coefficient being 100 results in p = 80. You might want to check your solver.

ps #2. Why do you want to introduce such a variable? Does it have a meaning in real-world?

link

answered 31 May '12, 11:08

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

Hey Ehsan,

1) You're absolutely right, sloppy copy and paste error on my part.

2) It's my artificial attempt to represent what's left over. Say my initial "0.05x + 0.02y + z = 1" constraint represents how £100 for investment is constrained across funds x, y and z, and their objective co-efficients represent a risk metric. So I want to minimise my risk while allocating as much of the £100 as possible across x, y and z. But it might not be possible to allocate all £100 to x, y, and z due other constraints like "z <= 0.5". So the sink1 decision variable would represent £43 that is left over in our above example (i.e. 0.43 => £43). Without sink1, the problem would be infeasible.

If I re-wrote the constraint from "0.05x + 0.02y + z + sink1 = 1" to "0.05x + 0.02y + z <= 1", this would better reflect what I'm trying to achieve I think. The problem with this is that the optimiser will just set all the decision variables to zero!

You could well be right about the sensitivity analysis but I'm not sure too be honest as I haven't had much practical experience with it as our custom solver is pretty basic and doesn't support it at the moment.

Thanks Ehsan.

Cheers, Rick

(31 May '12, 13:38) FionnMac

If my definition of the objective function sensitivity analysis is what you've in mind from "tipping point", I think you're good to go (see Taha's "Operations Research: An Introduction" or Hillier and Lieberman's "Introduction to Operations Research" for more information, but there're many resources on the web). Also, I've checked this with a solver with sensitivity analysis capabilities. You might try using demo versions of LINGO or GAMS for this with no cost. Also, if you've access to MS Excel, you could check it with that too.

http://people.brunel.ac.uk/~mastjjb/jeb/or/lpsens_solver.html

(31 May '12, 13:56) Ehsan ♦

@FionnMac: Please note that this is a Q&A website and not a discussion website. Therefore, please leave your answers to others' answers as comments and not answers. You could also enrich your original question with the more interesting information you just revealed.

(31 May '12, 14:02) Ehsan ♦
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
×4
×1
×1

Asked: 31 May '12, 09:36

Seen: 1,669 times

Last updated: 08 Jul '12, 16:47

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