Changes between Version 6 and Version 7 of AlkMod2017
 Timestamp:
 10/24/17 23:57:35 (2 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

AlkMod2017
v6 v7 2 2 3 3 == November 8. == 4 [attachment:garg97faster.pdf Naveen Garg, Jochen Konemann. ''Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems'']5 6 This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for mincost flow computations in computing maximum concurrent flow and mincost multicommodity flow; this yields much faster algorithms when the number of commodities is large.7 8 == November 15. ==9 4 [attachment:SolvingHuge.pdf C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W.P. Savelsbergh, P. H. Vance. ''BranchandPrice: Column Generation for Solving Huge Integer Programs''] 10 5 11 6 We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e. implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branchandbound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations and eliminates symmetry. We then discuss computational issues and implementation of column generation, branchandbound algorithms, including special branching rules and effient ways to solve the LP relaxation. 7 8 == November 15. == 9 10 [attachment:a02v29n2.pdf D. P. Ronconi and M. S. Kawamura. ''The single machine earliness and tardiness scheduling problem: lower bounds and a branchandbound algorithm''] 11 12 This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branchandbound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. 12 13 13 14 == November 22. == … … 16 17 17 18 == November 29. == 18 [attachment:a02v29n2.pdf D. P. Ronconi and M. S. Kawamura. ''The single machine earliness and tardiness scheduling problem: lower bounds and a branchandbound algorithm'']19 19 20 This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branchandbound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. 20 [attachment:garg97faster.pdf Naveen Garg, Jochen Konemann. ''Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems''] 21 22 This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for mincost flow computations in computing maximum concurrent flow and mincost multicommodity flow; this yields much faster algorithms when the number of commodities is large. 21 23 22 24 == December 6. ==