Branch & Converge: A Generic Technique for Boundable Problems (Bachelor Seminar)

To this end, we propose Branch & Converge, an abstract method applicable to problems over commutative, ordered monoids. Branch & Bound can be regarded as a specialization of Branch & Converge using the maximum (or minimum) operator. Our method requires that a problem can be partitioned and that a partitions total value can be efficiently bounded from above and below. It yields iteratively tightening bounds and terminates eventually with the exact solution. This talk gives a brief introduction and highlights the similarities to Branch & Bound. We then discuss one possible realization of our method. Based on recent works in the area of combinatorial optimization, we show that recursive models (as seen in dynamic programming) can be used to build approximate decision diagrams for problems over ordered semirings, yielding both upper and lower bounds. This procedure will be illustrated for the problem of counting feasible solutions.


---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.