  


Solving MIPs via Scalingbased Augmentation
Pierre Le Bodic (lebodicgatech.edu) Abstract: Augmentation methods for mixedinteger (linear) programs are a class of primal solution approaches in which a current iterate is augmented to a better solution or proved optimal. It is well known that the performance of these methods, i.e., number of iterations needed, can theoretically be improved by scaling methods. We extend these results by an improved and extended convergence analysis, which shows that bit scaling and geometric scaling theoretically perform similarly well in the worst case for 0/1 polytopes as well as show that in some cases geometric scaling can outperform bit scaling arbitrarily. We also investigate the performance of implementations of these methods, where the augmentation directions are computed by a MIP solver. It turns out that the number of iterations is usually low. While scaling methods usually do not improve the performance for easier problems, in the case of hard mixedinteger optimization problems they allow to compute solutions of very good quality and are often superior. Keywords: MIP, scaling, augmentation Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 09/10/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  