  


Safe bounds in linear and mixedinteger programming
Arnold Neumaier (Arnold.Neumaierunivie.ac.at) Abstract: Current mixedinteger linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre and postprocessing of the linear programs arising in a branchandcut framework can guarantee that no solution is lost, at least for mixedinteger programs in which all variables can be bounded rigorously by bounds of reasonable size. Keywords: Linear programming, mixedinteger programming, rounding errors, directed rounding, interval arithmetic, branchandcut, lower bounds, mixedinteger rounding, generalized Gomory cut, safe cuts, safe presolve, certificate of infeasibility. Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: http://www.mat.univie.ac.at/+AH4neum/papers.html#mip Download: [Compressed Postscript][PDF] Entry Submitted: 06/18/2002 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  