Originally posted by: SystemAdmin

Hi All,

I am trying to solve a network problem, trying to optimize the total cost of different parameters. I've modeled the problem as an MIP, and was trying different approaches to reduce the time taken for the problem to solve. The cplex 12.4 solver does a good job for specific problems of small size. However, for sufficient large problems the the solution takes a long time to converge.

I tried decomposing the problem using the Bender's decomposition method to solve(with certain refinements proposed by McDaniel & Devine (1977)) and got little success.
The Bender's Branch and Cut framework looks promising, however, in many cases my implementation (which is similar to the ATSP example provided by IBM) stops before termination, as the system runs out of memory. Therefore, I cant really be sure if this algorithm would be beneficial. Is there a good way to resolve this problem, and any other refinements that I can try out.

Also, another approach I was trying was to decompose the large networks into smaller sections, solve each separately and combine the solutions to get an initial solution for cplex to start. However, cplex somehow takes much longer time than the original problem itself, although the initial solution provided by me is feasible and complete (when verified manually). I am not totally sure, if my implementation is entirely correct. Could someone suggest the best and correct way to do this. I was using the setVectors() method to provide the initial solution.

Regards,
Vikranth.T
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Are you sure that the composition of the subproblem solutions is feasible in the full problem? If not, I think CPLEX will try to repair the starting solution you gave it, and it's anyone's guess how long that would take.

Other than that, the only thing that comes to mind is that, at least as of version 12.5, setVectors is deprecated in favor of addMIPStart, which I think was present in 12.4. If so, you might give that a try.

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

Yeah, I'm not sure I totally get the question. On running out of memory, I took this answer from a different thread:

In order to solve the out of memory issue you should use node files. Set parameter CPX_PARAM_WORKMEM to something like 500 MB and CPX_PARAM_NODEFILEIND to 3. These parameter settings will swap out parts of the tree to disk so that you do not run out of memory that early. Please also refer to the reference or user manual to understand what these parameter settings mean.

There might be more tricks. Just search "out of memory" in the forum. It's a common problem.

If the question is, "I implemented Bender's and it is slower than Cplex, what can I do?", then you might just be out of luck. Think of it like this -- If Bender's Decomposition outperformed Cplex frequently, wouldn't it be part of it's toolkit rather than an example problem? I bet it is much more likely to be slower than faster on general MIPs. If there is some reason you think Bender's would perform well (a paper where it was utilized on a problem like yours and compared to a recent cplex release or something in the problem structure) then keep at it. If not, you are more likely to improve performance by customizing Cplex's search, finding a good heuristic to give it initial solutions, etc than just forcing Bender's on it.
#CPLEXOptimizers
#DecisionOptimization