کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4636279 | 1340721 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane](/preview/png/4636279.png)
چکیده انگلیسی
This paper presents a new heuristic algorithm for general integer linear programming, in which the objective function is varied as a parameter. First of all, since the feasible region of the linear programming relaxation problem is intercepted by the objective function hyperplane to form a convex polyhedra for some fixed integral value of the objective function, the vertices on the polyhedron are determined and used to produce the value ranges of the variables by the expression of the linear convex combination of the vertices. In the value ranges it can be identified whether a feasible solution to the integer program exists or not. Next, a simple, ingenious linear transformation of the original problem into new variables is made and a so-called stopped search algorithm applied to finding the optimal solution or the fact that there is no feasible solution to the integer program on the objective function hyperplane. Comparing with some existing algorithms, our algorithm is more easier in computation in that it must not get all the extreme points of the feasible domain of the relaxation problem and not solve otherwise ordinary linear programming subproblems, and has a moderate memory requirement with the size of the problem. The computational experience in the numerical examples shows that the algorithm presented here is efficient, potential and hence is of great practical interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 185, Issue 1, 1 February 2007, Pages 301-311
Journal: Applied Mathematics and Computation - Volume 185, Issue 1, 1 February 2007, Pages 301-311
نویسندگان
Pei-wang Gao,