Integral Simplex Using Decomposition with Primal Cuts
作者： Samuel Rosat , Issmail Elhallaoui , François Soumis , Andrea Lodi
DOI: 10.1007/978-3-319-07959-2_3
关键词:
摘要: The integral simplex using decomposition (ISUD) algorithm [22] is a dynamic constraint reduction method that aims to solve the popular set partitioning problem (SPP). It special case of primal algorithms, i.e. algorithms furnish an improving sequence feasible solutions based on resolution, at each iteration, augmentation either determines direction, or asserts current solution optimal. To show how ISUD related we introduce new problem, MRA. We MRA canonically induces and deepens understanding ISUD. characterize cuts adapt this relate them cuts. These yield major improvement over ISUD, making mean optimality gap drop from 33.92% 0.21% some aircrew scheduling problems.
springer.com
acm.org 
sci-hub.st 参考文章(19)
Fred Glover, CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION, AN ALL-INTEGER INTEGER PROGRAMMING ALGORITHM Defense Technical Information Center. ,(1963) , 10.21236/AD0435043
Gerald L. Thompson, An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems Computational Optimization and Applications. ,vol. 22, pp. 351- 367 ,(2002) , 10.1023/A:1019758821507
Bianca Spille, Robert Weismantel, Primal Integer Programming Handbooks in Operations Research and Management Science. ,vol. 12, pp. 245- 276 ,(2005) , 10.1016/S0927-0507(05)12005-2
Matthias F. Stallmann, Franc Brglez, High-contrast algorithm behavior: observation, conjecture, and experimental design ecs'07 Experimental computer science on Experimental computer science. pp. 13- 13 ,(2007)
Andrea Lodi, Adam N. Letchford, Primal separation algorithms A Quarterly Journal of Operations Research. ,vol. 1, pp. 209- 224 ,(2003) , 10.1007/S10288-003-0012-8
Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler, 0/1-Integer Programming: Optimization and Augmentation are Equivalent european symposium on algorithms. pp. 473- 483 ,(1995) , 10.1007/3-540-60313-1_164
Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura, Primal Separation for 0/1 Polytopes Mathematical Programming. ,vol. 95, pp. 475- 491 ,(2003) , 10.1007/S10107-002-0309-Y
Ronald D. Koncal, Harvey M. Salkin, Set Covering by an All Integer Algorithm: Computational Experience Journal of the ACM. ,vol. 20, pp. 189- 193 ,(1973) , 10.1145/321752.321753
Ralph E. Gomory, Outline of an algorithm for integer solutions to linear programs Bulletin of the American Mathematical Society. ,vol. 64, pp. 275- 278 ,(1958) , 10.1090/S0002-9904-1958-10224-4
Adam N. Letchford, Andrea Lodi, Primal cutting plane algorithms revisited Mathematical Methods of Operations Research. ,vol. 56, pp. 67- 81 ,(2002) , 10.1007/S001860200200