@inproceedings{BertholdHeinzPfetschetal., author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc and Vigerske, Stefan}, title = {Large Neighborhood Search beyond MIP}, series = {Proceedings of the 9th Metaheuristics International Conference (MIC 2011)}, booktitle = {Proceedings of the 9th Metaheuristics International Conference (MIC 2011)}, isbn = {978-88-900984-3-7}, pages = {51 -- 60}, abstract = {Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.}, language = {en} } @inproceedings{BertholdHeinzPfetsch2009, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Nonlinear pseudo-Boolean optimization}, series = {Theory and Applications of Satisfiability Testing - SAT 2009}, volume = {5584}, booktitle = {Theory and Applications of Satisfiability Testing - SAT 2009}, editor = {Kullmann, Oliver}, publisher = {Springer}, pages = {441 -- 446}, year = {2009}, language = {en} } @inproceedings{BertholdPfetsch2009, author = {Berthold, Timo and Pfetsch, Marc}, title = {Detecting Orbitopal Symmetries}, series = {Operations Research Proceedings 2008}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {433 -- 438}, year = {2009}, language = {en} }