检索结果-内蒙古大学图书馆

New convergent heuristics for 0-1 mixed integer programming

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期195卷 62-74页

作者： Wilbaut, Christophe Hanafi, Said Univ Valenciennes Le Mt Houy ISTV2 LAMIH ROI F-59313 Valenciennes 9 France

Several hybrid methods have recently been proposed for solving 0-1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0-1 multidimensional Knapsack problem. Other encouraging results obtained for 0-1 MIP problems are also presented. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Relaxation 0-1 mixed integer programming Heuristic Multidimensional Knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

引用

MATHEMATICAL programming 2003年第1-3期98卷 115-143页

作者： Richard, JPP de Farias, IR Nemhauser, GL Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Carnegie Mellon Univ Grad Sch Ind Adm Pittsburgh PA 15213 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds. We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.

关键词： 0-1 mixed integer programming polyhedral theory superlinear lifting

来源：评论

学校读者我要写书评

暂无评论

Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

引用

MATHEMATICAL programming 2003年第1-3期98卷 89-113页

作者： Richard, JPP de Farias, IR Nemhauser, GL Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Ctr Operat Res & Econometr B-1348 Louvain Belgium

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables. We develop a lifting theory for the continuous variables. In particular, we present a pseudo-polynomial algorithm for the sequential lifting of the continuous variables and we discuss its practical use.

关键词： 0-1 mixed integer programming polyhedral theory lifting

来源：评论

学校读者我要写书评

暂无评论

Hybrid variable neighbourhood decomposition search for 0-1 mixed integer programming problem

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 883-890页

作者： Hanafi, Saïd Lazić, Jasmina Mladenović, Nenad Wilbaut, Christophe Crévits, Igor LAMIH - Universite de Valenciennes ISTV 2 Le Mont Houy 59313 Valenciennes Cedex 9 France Brunel University West London UB8 3PH United Kingdom

In this paper we propose new hybrid heuristics for the 0-1 mixed integer programming problem, based on the variable neighbourhood decomposition search principle and on exploiting information obtained from a series of relaxations. In the case of a maximization problem, we add iteratively pseudo-cuts to the problem in order to produce a sequence of lower and upper bounds of the problem, so that integrality gap is reduced. We validate our approaches on the well-known 0-1 multidimensional knapsack problem, in which the general-purpose CPLEX MIP solver is used as a black box for solving subproblems generated during the search process. The results obtained with these methods are comparable with the current state-of-the-art heuristics on a set of large scale instances. © 2010 Elsevier B.V.

关键词： 0-1 mixed integer programming Multidimensional Knapsack Problem Variable Neighbourhood Search

来源：评论

学校读者我要写书评

暂无评论

Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

Lifted inequalities for 0-1 mixed integer programming: Basic...

引用

Workshop on integer programming

作者： Richard, JPP de Farias, IR Nemhauser, GL Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Ctr Operat Res & Econometr B-1348 Louvain Belgium

关键词： 0-1 mixed integer programming polyhedral theory lifting

来源：评论

学校读者我要写书评

暂无评论

Variable neighbourhood pump heuristic for 0-1 mixed integer programming feasibility

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 759-766页

作者： Hanafi, Saïd Lazić, Jasmina Mladenović, Nenad Brunel University West London UB8 3PH United Kingdom LAMIH - Universite de Valenciennes ISTV 59313 Valenciennes Cedex 9 2 Le Mont Houy France

In this paper we propose a new method for finding an initial feasible solution for mixed integer programs. We call it "Variable neighborhood pump", since it combines ideas of Variable neighborhood branching and Feasibility pump heuristics. The proposed heuristic was tested on an established set of 83 benchmark problems proven to be difficult to solve to feasibility. The results are compared with those of IBM ILOG CPLEX 11.1, which already includes standard feasibility pump as a primal heuristic. With our approach we managed to obtain better initial objective function values than CPLEX on 63 test instances, within similar average computational time. © 2010 Elsevier B.V.

关键词： 0-1 mixed integer programming Constructive Heuristics CPLEX Feasibility Pump Variable Neighbourhood Search

来源：评论

学校读者我要写书评

暂无评论

Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting

Lifted inequalities for 0-1 mixed integer programming: Super...

引用

Workshop on integer programming

关键词： 0-1 mixed integer programming polyhedral theory superlinear lifting

来源：评论

学校读者我要写书评

暂无评论

Routing of barge container ships by mixed-integer programming heuristics

引用

APPLIED SOFT COMPUTING 2013年第8期13卷 3515-3528页

作者： Maras, Vladislav Lazic, Jasmina Davidovic, Tatjana Mladenovic, Nenad Univ Belgrade Fac Transport & Traff Engn Belgrade Serbia Serbian Acad Arts & Sci Math Inst Belgrade Serbia Brunel Univ Dept Math London England MathWorks Inc Cambridge CB4 0HH England

We investigate the optimization of transport routes of barge container ships with the objective to maximize the profit of a shipping company. This problem consists of determining the upstream and downstream calling sequence and the number of loaded and empty containers transported between any two ports. We present a mixed integer linear programming (MILP) formulation for this problem. The problem is tackled by the commercial CPLEX MIP solver and improved variants of the existing MIP heuristics: Local Branching, Variable Neighborhood Branching and Variable Neighborhood Decomposition Search. It appears that our implementation of Variable Neighborhood Branching outperforms CPLEX MIP solver both regarding the solution quality and the computational time. All other studied heuristics provide results competitive with CPLEX MIP solver within a significantly shorter amount of time. Moreover, we present a detailed case study transportation analysis which illustrates how the proposed approach can be used by managers of barge shipping companies to make appropriate decisions and solve real life problems. (C) 2013 Elsevier B. V. All rights reserved.

关键词： Routing Barge container ships Empty containers 0-1 mixed integer programming Meta-heuristics

来源：评论

学校读者我要写书评

暂无评论

Variable neighbourhood decomposition search for 0-1 mixed integer programs

引用

COMPUTERS & OPERATIONS RESEARCH 2010年第6期37卷 1055-1067页

作者： Lazic, Jasmina Hanafi, Said Mladenovic, Nenad Urosevic, Dragan Univ Valenciennes LAMIH F-59313 Valenciennes 9 France Brunel Univ Uxbridge UB8 3PH Middx England Serbian Acad Arts & Sci Math Inst Belgrade 11000 Serbia

In this paper we propose a new hybrid heuristic for solving 0-1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： 0-1 mixed integer programming Metaheuristics Variable neighbourhood search CPLEX

来源：评论

学校读者我要写书评

暂无评论

Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第1期39卷 32-41页

作者： Crevits, Igor Hanafi, Saied Mansi, Raied Wilbaut, Christophe Univ Valenciennes & Hainaut Cambresis LAMIH F-59313 Valenciennes France Univ Lille Nord France F-59000 Lille France CNRS FRE 3304 F-59313 Valenciennes France

Recently several hybrid methods combining exact algorithms and heuristics have been proposed for solving hard combinatorial optimization problems. In this paper, we propose new iterative relaxation-based heuristics for the 0-1 mixed integer programming problem (0-1 MIP), which generate a sequence of lower and upper bounds. The upper bounds are obtained from relaxations of the problem and refined iteratively by including pseudo-cuts in the problem. Lower bounds are obtained from the solving of restricted problems generated by exploiting information from relaxation and memory of the search process. We propose a new semi-continuous relaxation (SCR) that relaxes partially the integrality constraints to force the variables values close to 0 or 1. Several variants of the new iterative semi-continuous relaxation based heuristic can be designed by a given update procedure of multiplier of SCR. These heuristics are enhanced by using local search procedure to improve the feasible solution found and rounding procedure to restore infeasibility if possible. Finally we present computational results of the new methods to solve the multiple-choice multidimensional knapsack problem which is an NP-hard problem, even to find a feasible solution. The approach is evaluated on a set of problem instances from the literature, and compared to the results reached by both CPLEX solver and an efficient column generation-based algorithm. The results show that our algorithms converge rapidly to good lower bounds and visit new best-known solutions. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： 0-1 mixed integer programming Multiple-choice multidimensional knapsack problem Semi-continuous relaxation Hybrid method

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：