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 coeffiecent 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 online 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: All good so far. But now say 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 coeffecient 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: The key here is that the objective coeffecient of the In our example, the "tipping" point happens when the objective coeffecient of So in our example, we introduce The fun (finally!) begins when I try to apply this to a problem with two nonupper 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: 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 coefficient 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 coefficients 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 coefficient 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 coefficient by at least the allowable increase value (probably more), resolve, 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! 
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 realworld? answered 31 May '12, 11:08 Ehsan ♦ 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 coefficients 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 rewrote 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 ♦

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".