Originally posted by: SystemAdmin

[muhamedaga said:]

Hi All;

I would need to implement a custom column pricing routine in order to help performance with an MILP problem.
Please let me know if you have done something like that and/or have some suggestion as how to go about it.


Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

I guess what you mean is to modify the pricing step of the simplex algorithm, right?

This is basically impossible to do with the CPLEX callbacks, and I doubt that you can do it in any other MIP solver for which you do not have source code access. The only option is to use the solve callback and basically implement your own simplex solver.

But I have another suggestion: tell us what your pricing strategy is and why you think that it is superior to the CPLEX strategies. Then, send us some models on which you think the pricing strategy should be superior. Maybe you have found something that we can implement for the next CPLEX release.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[muhamedaga said:]

Thanks for the reply.

The model has a large number of piecewise linear functions in the objective with thousands of segments. This brings number of columns of the problem over 10M, which gets me over time limit for solution.

I suppose cplex spends a good amount of time pricing these columns, i.e. choosing the candidate to enter the basis. But as the columns corresponding to the segments are identical except for the objective coefficient, one would essentially need to price out just one. I suspect the cplex will do many more if not all of them, depending on the pricing strategy.

So, if I could get control of the pricing, I assume, I could save a ton of time ( retrieving a column, backward/ forward substitution, etc. with a large number of columns this adds up).




#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

If I understand you correctly, your objective function is piecewise linear but still continuous (i.e., without any break points where the value jumps). I further assume that the objective function is convex (in the minimization case). What you are doing is essentially to use something like this:

min c1*x1 + c2*x2 + ... + cn*xn
s.t.
    x = x1 + x2 + ... + xn
    ... other constraints that involve x ...
bounds
    0 <= x1 <= p1<br />    0 <= x2 <= p2-p1<br />    0 <= x3 <= p3-p2<br />    ...
    0 <= xn <= pn-p(n-1)<br />
with c1 < c2 < ... < cn and p1 < p2 < ... < pn. Is this correct?<br />
So, what you are saying is that in the pricing procedure one just needs to check reduced costs for xi in increasing order of i. If xk has non-negative reduced costs, one does not need to look at xj, j > k, because these have larger reduced costs, namely rj = rk + cj - ck.

This is an interesting observation, and it should be possible to exploit this structure automatically. Certainly, we can identify the parellel column vectors. Could you please send us some version of your model (if possible, in different sizes) such that we can try to implement and test this idea?

Thanks,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[muhamedaga said:]

Yes, that's exactly the idea. Let's connect off-line. Thanks, Aga
#CPLEXOptimizers
#DecisionOptimization