I'm a beginner in C++ and want to implement Benders decomposition in C++ using CPLEX. I'm gonna use it for a special case study, so I need to customize the cuts to minimize the optimality gap. However, I don't know much about implementation. I was wondering if anyone can suggest a reference (books, papers, codes) begin with.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Welcome to OR SE. What do you mean by "customize the cuts"? $\endgroup$– prubin ♦Jan 20 at 22:03
-
$\begingroup$ Thanks Dr. Rubin, well I'm trying to seperate my single subproblem to multi problems, so I can add multiple cuts to master problem. More cuts I add at each iteration to master problem, more possibility I have to reach optimum solution. However, if I add too much cuts, it can increase run time, so there is a trade off. Therefore, After seperating subproblems, I want to find a linear combination of cuts (lets say just optimality cuts) to reduce computational time. Moreover, I'm looking for lazy and surrogate constraints,too. I will compare them at the end :) $\endgroup$– ValaJan 21 at 0:54
-
$\begingroup$ I've recently learn about benders implementation in C++ using CPLEX. What I'm not aware of is how much flexibility I have to add these accelerations to my benders approach, if I use CPLEX benders strategy. If there is non, maybe I need to implement Benders manually. $\endgroup$– ValaJan 21 at 0:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I think I just answered this on my blog, but for the record, CPLEX does not (as far as I know) provide access to Benders cuts when the problem is partitioned automatically using annotations. So to merge cuts from subproblems, you would need to employ callbacks.
There are two things to note regarding the idea of taking a linear combination of cuts. First, the combined cut likely would be weaker than the individual cuts, so any reduction in computational time from keeping the number of cuts smaller might well be offset by requiring more iterations in the master problem (and possibly more calls to the callback). Second, CPLEX automatically does some cut management. The cuts are added to a cut pool, and the ones that are nonbinding (for some number of iterations) are held out of the "working set" and only checked when necessary. So adding $K$ cuts does not necessarily mean that the master problem constraint matrix being used for pivoting has $K$ rows more than it started with.
-
$\begingroup$ Thanks for quick response. I guess it maybe better to stick to traditional way and see what is goinig on. $\endgroup$– ValaJan 21 at 17:22