Originally posted by: Eumpfenbach

I've spent a ton of time messing around with bender's decomposition and column generation and have not been able to compete with Cplex. Rather than blindly tackling a new problem, I was hoping for some advice:

Consider a technology selection problem. The each variable represents a combination of technologies to choose (which could be very large -- hundreds of thousands of combinations to millions). The rows represent the objectives of the technologies (cost, for example. There might be tens to hundreds of rows). The goal is to choose a single technology set so I am guessing that the linear relaxation will be integral. If not, it will be a small search tree. The objective is based on the slack values of the constraints.

I was thinking of solving this with a column generation approach on the subproblem(s). Start with a likely set of columns, solve, calculate the reduced cost of the columns that are not in the set, and reoptimize if the reduced costs tell me to. I would probably use Matlab to call cplex and do the calculations.

The question -- Is this likely to solve the problem quicker than cplex or am I essentially replicating what cplex already does and I would at best be equal to it? Any advice is appreciated.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

OK no answer, so I just did this. Now my question has turned from a "general guidance" one to more specific.

I have seen it mentioned in multiple threads that the values of the reduced costs must be accounted for in column generation. There must be something I am not understanding. I solve the problem with a subset of the columns and get a dual vector (y). I price in columns with their reduced cost c - A'y (for each column not included in the restricted problem). Any columns with a negative reduced cost, have potential to lower my objective value.

Now, the solution to the restricted problem also gives me positive values in the Solution.reducedcost field (I am using Matlab syntax). These reduced costs are attributed to the bounds of the variables that are in the restricted problem. So they could be removed as bounds and written as x <= ub, and the dual of this constraint would be the same as the reduced cost when included as a bound.

So, why would this reduced cost value have any impact on the pricing of columns since the coefficients in each column that is associated with that dual value will always be zero? Ie, consider a 2 variable problem where the upper bound for the first variable has been transformed into a standard constraint.

A = [A1 A2
A3 A4
A5 0 ]

b = [b1
b2
ub1]

So I solve with the first column in the restricted problem. The reduced cost of the second column is c2 - (A2*y1 + A4*y2 + 0 * y3). That last coefficient will always be zero. So why would I need to bother with the reduced costs ever? What am I missing?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I agree with what you wrote in the sequel ... but I also don't know what source you're citing for a need to use the reduced costs. Perhaps that source referred to a different problem/context/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: Eumpfenbach

Thanks for the response, Paul. I ask questions when I am stuck but don't just wait for this board (just in case it doesn't get answered).

You are correct in that it is a VERY easy problem to solve. It is also one that I would like to be solved very, very quickly.

Also, I had some duals in a loop that weren't getting properly updated. So my CG technique was correct (even if it is overkill).

So I'm good (on this topic). Thanks again.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If each column represents a combination of technologies, and you're looking for a single technology "set", does that mean you solution will use a single column? (Are the variables binary - select this column or not?) If so, you're just looking for the column with the best score on some linear function. Assuming you have a way to generate columns, this sounds more like a search than an optimization problem. So maybe I'm misinterpreting something.

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