# LP formulation problem: "sink" decision variables to prevent infeasibility

 2 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 33●4 accept rate: 0% fbahr ♦ 4.6k●7●16 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 ♦♦

 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: