Originally posted by: Eumpfenbach

I am a PhD student. I want to be able to publish some work in a good journal (as I'm sure most of the posters on here do). I have a Mixed Integer Problem I am trying to solve efficiently. I used Bender's Decomposition first. CPLEX was still faster. I tried implementing my cuts through callbacks. Still, CPLEX is faster.

I recently tried column generation on my linear problem to see how much I could speed it up. A standard cplex solve takes .29 seconds. If I only track the time spent solving problems, with column generation I can cut the time down to .15 seconds. However, when I track total time (ie solving, getting the duals, iterating over a for loop to calculate the potential each column added has to help the objective function, adding the columns to the master problem, etc...) the total time goes up to 1.5 seconds.

So I guess I am asking for tips on how to be a good programmer with cplex. If I jump from python to C, will there likely to be a nice increase in speed? Is what I described typical? It seems like the decomposition methods in general seem to be effective, but they get killed by all the time spent interfacing and doing things like creating intermediate vectors for the subproblems, whereas cplex generates all its cuts efficiently and internally.

My problem doesn't really have a special structure. I chose one that is outside of the classical problems (ie not a traveling salesman, knapsack, etc...). Since cplex is designed to be an industrial strength general MIP solver, am I likely to ever be able to improve on it?

Any tips or advice would be greatly appreciated. I have spent months trying to beat cplex and can't do it. It's a negative for me and my work, but also a positive reinforcement of how good a tool it is...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Improving on CPLEX for general mixed integer programs is hard. I try it every day (with access to internals) and often fail. Researchers across the world try it, and sometimes interesting ideas are generated that have some potential. Then we would pick them up and try them internally.

I think the best chance to improve on CPLEX is to focus on a particular class of models where you can really exploit the structure. The more knowledge about your problem you can get into your special algorithms, the better. Find good primal heuristics, investigate the polyhedral structure of your problem to find good cutting plane separators, implement special presolving techniques, or invent a branching rule that fits to the structure of the problem.

Regarding column generation, if the full problem is already solved by standard CPLEX in .29 seconds, I don't see much value in a column generation approach. Column generation is usually applied when the full problem has a huge number of columns but in an optimal solution only a very small fraction of them have a non-zero value.

If you are really looking for top performance, then you should go through the C API, in particular the 64 bit CPXX methods that have been added with CPLEX 12.3. This has the smallest amount of overhead.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Thank you for your response. I am aware of when column generation is likely to succeed. I was kind of trying to just take a stab and hope. I hope to one day solve LP problems that are much bigger. I used it as a general example of frustration in trying to compete with cplex (ie getting killed with overhead).

I guess I have to reevaluate my overall strategy and the problem I want to solve. Thanks again for the advice.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Quick question about timing:

I run my script using cProfile module in python for timing. For example, there are two entries for getx:

8775690  116.239    0.000  116.239    0.000 {cplex._internal.py26_cplex123.CPXXgetx}

and

8775690   21.951    0.000  307.394    0.000 _subinterfaces.py:7195(getx)

Would I be correct if I assumed that if I coded my problem in C that the speedup (only considering the timing regarding retrieving the values of variables) would be 21.951 seconds (ie CPXXgetx is the basic cplex function, getx can be attributed to the python API interacting with cplex)?

I am hoping I can report my times as if it was coded in C but still utilize the easier functionality of the Python API. Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Sorry, in case anyone isn't familiar with cProfile, these are the headers:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You are right CPXXgetx() is the callable library function that is invoked by the Python wrapper and getx() is the Python function that wraps around the callable library function.
So when coding directly in C you will not have the getx() overhead.
Whether you would indeed save 21.951 seconds when implementing everything in C I am not sure. This highly depends on the accuracy of the profiling tool you used. And maybe also on the overhead the profiling tool itself adds?
Did I understand correctly: You want to time the execution time of your application, then subtract all times that are spent in Python-only functions and then claim that the resulting time would be the running time if you implemented everything in C? I don't think that this is valid reasoning. There may be things you would have to add in C after you removed all Python overhead (for example for handling all your data).
This sounds more like cheating to me :-)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Yeah I agree it is tricky. I am assuming the profiling tool has a negligible impact on script time. I would err on the side of caution in only removing times that I can directly assign to the wrappers (not times doing things like building matrices in python that I use in my decomposition methods). I THINK it can be done honestly. I will have to clear with my advisor.

At this point, it doesn't really matter anyways. Taking out 60 seconds attributed to wrappers cplex is still 4 times faster.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Why you want to beat CPLEX for a problem which can be solved in less than a second? I think there is not that much there.
I believe it is impossible to beat CPLEX for small problems, so you need to try some large instances. At this case, there is a much better chance to be successful.
#CPLEXOptimizers
#DecisionOptimization