5
$\begingroup$

I have been using the method of fixing nonbasic variables with non-zero reduced costs to do preemptive goal programming. It works for the most part. But I have recently noticed in a certain instance of the problem, few variables have solution of 0, and their reduced cost is 0 too. I thought if the solution is 0, it is a non-basic variable. But when I used the commands available within cplex interactive optimizer, it showed me that these variables were still basic variables, but with solution 0. Since the preemptive goal programming method only fixes the non-basic variables with non zero reduced costs to 0, these variables escape the fixing, and while optimizing the next goal, the previously optimized objective deteriorates in value.

I think I am missing something very simple here, but I am not sure. Is it:

  1. fixing non-basic variables with non-zero variables is not enough to keep the optimality of the optimized objective?
  2. definition of nonbasic is not equal to those variables whose values are 0?

The method used here for the goal program is also known as column-dropping method. I wonder if the column-dropping approach does not work well for problems that have degenerate solutions.

$\endgroup$
  • 3
    $\begingroup$ 2: a variable can be basic with value $0$, in this case the solution is called degenerated. It occurs when multiple constraints intersect. $\endgroup$ – Kuifje Feb 7 at 9:06
  • $\begingroup$ @Kuifje thank you. I wonder if the method of fixing non-basic variables with non-zero variables fails to keep the objective's optimality in cases where solution is degenerate. $\endgroup$ – naveen divakaran Feb 7 at 14:26
  • $\begingroup$ This is what I learnt today. I observed the problem that triggered this question, does keep the optimum value even though the solution is degenerate. I have been using a tolerance to limit the upper bound on non-basic variables with non-zero reduced cost, because of the computing with limited precision requires me to not completely drop the column, to prevent infeasibilities. When i reduced the tolerance to low number to bring behavior close to column dropping the optimum of previous objective is preserved. Should I remove the question,or still keep it or paste this comment as answer? $\endgroup$ – naveen divakaran Feb 11 at 0:58
  • $\begingroup$ I think you could paste your comment as an answer :) $\endgroup$ – Kuifje Feb 11 at 8:13
1
$\begingroup$

I think I have answered my own question over the last day. I found that fixing non-basic variable with non-zero reduced was enough to keep the optimal value of higher priority goals.

The reason I was not getting the solution to retain the higher priority goal's optimality was due to a different reason. I have been using a tolerance to limit the upper bound on non-basic variables with non-zero reduced costs. The reason I was doing this was the math model that I was optimizing is highly ill-conditioned. If I did a simple column-dropping approach, I would have created an infeasibility in the models that I would optimize for left over goals. When i reduced the tolerance from current value to a lower value to bring behavior closer to column- dropping the optimum of previous objective is preserved.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.