  


A feasible rounding approach for mixedinteger optimization problems
Christoph Neumann (christoph.neumannkit.edu) Abstract: We introduce granularity as a sufficient condition for the consistency of a mixedinteger optimization problem, and show how to exploit it for the computation of feasible points: For optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixedinteger problem. Thus, the resulting feasible rounding approach is deterministic and even efficient, i.e., it computes feasible points in polynomial time. The optimization problems appearing in the feasible rounding approaches have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics, as long as the problem is granular. For instance, the computational cost of our approach always corresponds to merely a single step of the feasibility pump. A computational study on optimization problems from the MIPLIB libraries demonstrates that granularity may be expected in various real world applications. Moreover, a comparison with Gurobi indicates that state of the art software does not always exploit granularity. Hence, our algorithms do not only possess a worstcase complexity advantage, but can also improve the CPU time needed to solve problems from practice. Keywords: Rounding; granularity; inner parallel set; consistency Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Computational Optimization and Applications, 2018, DOI 10.1007%2Fs105890180042y Download: Entry Submitted: 12/08/2017 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  