Originally posted by: Eumpfenbach

I have a minimization problem. All constraints Ax<= b, x>= 0. I solve the full problem in matlab using cplex and record the nonzero columns (using find(lp.Solution.x ~= 0)).

I then start over and create a problem using only the columns I found to be nonzero in the previous problem. I price the columns left out (using c - A*dual) and find variables with large negative reduced costs. Say I bring in the variable with the largest negative reduced cost. I resolve. I find that the new variable has value 0 in the next solution, 0 reduced cost, and the objective value doesn't change. Is this normal? The new variable should participate in the basis of the next problem, correct?

Can anyone help me make sense of this?

thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Suppose your initial solution is degenerate. By including in the reduced problem only variables with nonzero values in the original solution, you may omit at least variable that was basic in that solution (depending on whether any of the "natural" variables was basic at zero -- in other words, whether the optimal solution lay on any of the coordinate hyperplanes). Since the constraint set is unchanged, the number of basic variables is unchanged, so some other variable is elected to be basic. When you price the variable you omitted, it looks attractive because it belongs in the basis. When you pivot it in, it comes in at zero because that's its optimal value.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I suspected degeneracy but wanted an expert's opinion. Thanks!

Follow up question -- is there anything I can do to detect/prevent this? Without knowing the nonzero variable set to start (ie, cheating) there is no way to know whether a variable will pivot in at zero or not, right?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Don't know about MATLAB, but other APIs have methods that return the basis status of each variable. If you retain all basic columns, whether zero or not, I think you would solve your issue (?).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

In matlab, if you use Cplex class, after you solved your model, then a field named Start in Cplex object will be populated, in which, you can find the basis status of cols and rows.
John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Pardon me if I am not understanding correctly, but retaining the whole basis matrix is equivalent to having the problem solved (or at least, the column generating part of it). I only start with the nonzero variables as a way of testing my script. Really, I need to be able to start with any suboptimal guess and find the optimal solution.

My question is, is there any way of determining whether a variable will be nonzero before I bring it in to the master problem? Even if I bring it in and it takes a zero value, I can't guarantee that bringing in other variables later won't make it nonzero, correct? If it is zero over a certain number of iterations I could probably remove it, but nothing is for certain.

I have a basis of 200,000 variables, only about 3000 of which are nonzero. I only really care about the nonzero ones. Having to spend a ton of time pricing and bringing in the extra variables will kill my algorithm time. Maybe the best algorithm would be something like this:

1) price in the variables
2) if a variable takes on a zero value over so many iterations, remove it into a separate pool
3) hopefully find an optimal or near optimal solution quickly without a large number of the basic, but zero-valued columns taking up computation time
4) bring in all the basic columns (to prove optimality). There should be very little pivoting needed and it should hopefully converge quickly.
I realize I wrote a lot in this message. Just trying to get my thoughts out there so that the experts can tell me if any of my assumptions are wrong or there are better ways of doing things. Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

At each iteration, you will need a dual "solution" in order to price columns. In the last iteration, you will need an optimal dual solution. How are you proposing to generate dual solutions without having a full basis?

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If your basis is 98.5% zeros, you might consider using an interior point algorithm.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization