کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4959060 1445467 2017 47 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
ترجمه فارسی عنوان
یک چارچوب اکتشافی مبتنی بر برنامه نویسی خطی برای کمینه کردن حداکثر کمینه با کمترین هزینه با هزینه های فاصله
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
This work deals with a class of problems under interval data uncertainty, namely interval robust-hard problems, composed of interval data min-max regret generalizations of classical NP-hard combinatorial problems modeled as 0-1 integer linear programming problems. These problems are more challenging than other interval data min-max regret problems, as solely computing the cost of any feasible solution requires solving an instance of an NP-hard problem. The state-of-the-art exact algorithms in the literature are based on the generation of a possibly exponential number of cuts. As each cut separation involves the resolution of an NP-hard classical optimization problem, the size of the instances that can be solved efficiently is relatively small. To smooth this issue, we present a modeling technique for interval robust-hard problems in the context of a heuristic framework. The heuristic obtains feasible solutions by exploring dual information of a linearly relaxed model associated with the classical optimization problem counterpart. Computational experiments for interval data min-max regret versions of the restricted shortest path problem and the set covering problem show that our heuristic is able to find optimal or near-optimal solutions and also improves the primal bounds obtained by a state-of-the-art exact algorithm and a 2-approximation procedure for interval data min-max regret problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 81, May 2017, Pages 51-66
نویسندگان
, , , ,