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

The piecewise linear optimization polytope: new inequalities and intersection with semi-continuous constraints

MATHEMATICAL programming 2013年第1-2期141卷 217-255页

作者： Zhao, Ming de Farias, Ismael Regis, Jr. SAS Cary NC USA Texas Tech Univ Dept Ind Engn Lubbock TX 79409 USA

We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.

关键词： Piecewise linear optimization mixed-integer programming Knapsack problem Special ordered set Semi-continuous variables Polyhedral method Branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A polyhedral study of the semi-continuous knapsack problem

引用

MATHEMATICAL programming 2013年第1-2期142卷 169-203页

作者： de Farias, Ismael Regis, Jr. Zhao, Ming Texas Tech Univ Dept Ind Engn Lubbock TX 79409 USA SAS Cary NC USA

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Such structure arises in a wide variety of important problems, e. g. blending and portfolio selection. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts, we present computational results on real instances of the unit commitment problem, as well as on a number of randomly generated instances of linear programming with semi-continuous variables.

关键词： Semi-continuous variables mixed-integer programming Disjunctive programming Polyhedral combinatorics Branch-and-cut Unit commitment problem

来源：评论

学校读者我要写书评

暂无评论

A new MILP-based approach for unit commitment in power production planning

引用

INTERNATIONAL JOURNAL OF ELECTRICAL POWER & ENERGY SYSTEMS 2013年第1期44卷 997-1005页

作者： Viana, Ana Pedroso, Joao Pedro Inst Politecn Porto INESC TEC Oporto Portugal Inst Politecn Porto Inst Super Engn Oporto Portugal Univ Porto INESC TEC Oporto Portugal Univ Porto Fac Ciencias Oporto Portugal

s This paper presents a complete, quadratic programming formulation of the standard thermal unit commitment problem in power generation planning, together with a novel iterative optimisation algorithm for its solution. The algorithm, based on a mixed-integer formulation of the problem, considers piecewise linear approximations of the quadratic fuel cost function that are dynamically updated in an iterative way, converging to the optimum: this avoids the requirement of resorting to quadratic programming, making the solution process much quicker. From extensive computational tests on a broad set of benchmark instances of this problem, the algorithm was found to be flexible and capable of easily incorporating different problem constraints. Indeed, it is able to tackle ramp constraints, which although very important in practice were rarely considered in previous publications. Most importantly, optimal solutions were obtained for several well-known benchmark instances. including instances of practical relevance, that are not yet known to have been solved to optimality. Computational experiments and their results showed that the method proposed is both simple and extremely effective. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Combinatorial optimisation mixed-integer programming Unit commitment

来源：评论

学校读者我要写书评

暂无评论

Approximating the Split Closure

引用

INFORMS JOURNAL ON COMPUTING 2013年第4期25卷 808-819页

作者： Fischetti, Matteo Salvagnin, Domenico Univ Padua Dept Informat Engn I-35131 Padua Italy

The split closure has been proved in practice to be a very tight approximation of the integer hull formulation of a generic mixed-integer linear program. However, exact separation procedures for optimizing over the split closure have unacceptable computing times in practice;hence, many different heuristic strategies have been proposed in the last few years. In this paper we present a new overall framework for approximating the split closure that merges different ideas from the previous approaches. Computational results prove the effectiveness of the proposed procedure compared to the state of the art, showing that a good approximation of the split closure bound can be obtained with very reasonable computing times.

关键词： mixed-integer programming Gomory cuts split cuts

来源：评论

学校读者我要写书评

暂无评论

Spatially Efficient Design of Annotated Metro Maps

引用

COMPUTER GRAPHICS FORUM 2013年第3期32卷 261-270页

作者： Wu, Hsiang-Yun Takahashi, Shigeo Hirono, Daichi Arikawa, Masatoshi Lin, Chun-Cheng Yen, Hsu-Chun Univ Tokyo Tokyo 1138654 Japan Natl Chiao Tung Univ Hsinchu Taiwan Natl Taiwan Univ Taipei Taiwan

Annotating metro maps with thumbnail photographs is a commonly used technique for guiding travelers. However, conventional methods usually suffer from small labeling space around the metro stations especially when they are interchange stations served by two or more metro lines. This paper presents an approach for aesthetically designing schematic metro maps while ensuring effective placement of large annotation labels that are sufficiently close to their corresponding stations. Our idea is to distribute such labels in a well-balanced manner to labeling regions around the metro network first and then adjust the lengths of metro line and leader line segments, which allows us to fully maximize the space coverage of the entire annotated map. This is accomplished by incorporating additional constraints into the conventional mixed-integer programming formulation, while we devised a three-step algorithm for accelerating the overall optimization process. We include several design examples to demonstrate the spatial efficiency of the map layout generated using the proposed approach through minimal user intervention.

关键词： Metro maps annotation labels efficient space coverage mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

A Pareto-based hybrid multiobjective evolutionary approach for constrained multipath traffic engineering optimization in MPLS/GMPLS networks

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2013年第4期36卷 1196-1207页

作者： El-Alfy, El-Sayed M. Mujahid, Syed N. Selim, Shokri Z. King Fand Univ Petr & Minerals Coll Comp Sci & Engn Dhahran 31261 Saudi Arabia

This paper proposes a hybrid evolutionary algorithm for solving the constrained multipath traffic engineering problem in MPLS (Multi-Protocol Label Switching) network and its extended architecture GMPLS (Generalized MPLS). Multipath traffic engineering is gaining more importance in contemporary networks. It aims to satisfy the requirements of emerging network applications while optimizing the network performance and the utilization of the available resources within the network. A formulation of this problem as a multiobjective constrained mixed-integer program, which is known to be NP-hard, is first extended. Then, we develop a hybrid heuristic algorithm based on combining linear programming with a devised Pareto-based genetic algorithm for approximating the optimal Pareto curve. A numerical example is adopted from the literature to evaluate and compare the performance of six variations of the proposed heuristic. We study the statistical significance of the results using Kruskal-Wallis nonparametric test. We also compare the results of the heuristic approach with the lexicographic weighted Chebyshev method using a variety of performance metrics. (c) 2013 Elsevier Ltd. All rights reserved.

关键词： Traffic engineering Constrained multipath routing Load balancing Generalized/Multi-Protocol Label Switching Multiobjective optimization Evolutionary algorithms mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing

引用

COMPUTERS & CHEMICAL ENGINEERING 2013年 55卷 28-39页

作者： Velez, Sara Maravelias, Christos T. Univ Wisconsin Dept Chem & Biol Engn Madison WI 53706 USA

Exploiting multiple cores in a computer or grid of computers can reduce the time required to solve a mixed-integer programming (MIP) model. Here, we develop a parallel branch-and-bound algorithm for a chemical production scheduling problem using a discrete-time model. The algorithm consists of initialization, submission, branching, collection, bounding, and pruning steps. We branch by adding a constraint to bound the total number of times each task runs. Each subproblem is solved as an MIP on a single core of a computer, so that many sub problems can be solved simultaneously. Also, we propose an algorithm, executed at each node of our branch-and-bound tree, to improve the bounds on the number of times a task is run based on the current objective value. We present computational results for several instances to show the parallel algorithm with the proposed branching strategy can solve more challenging problems than simply using the default parallel option. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Chemical production scheduling mixed-integer programming Parallel computing

来源：评论

学校读者我要写书评

暂无评论

A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts

引用

JOURNAL OF SCHEDULING 2013年第5期16卷 443-460页

作者： Elahipanah, Mahsa Desaulniers, Guy Lacasse-Guay, Eve Ecole Polytech Montreal PQ H3C 3A7 Canada Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada HEC Montreal Montreal PQ Canada

In the service industry, workers perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of regular employees are often established several weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands are unveiled with more certainty, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving workers' meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step, which also involves assigning activities and tasks to the scheduled work shifts. To produce good-quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed-integer programming model is used to suggest temporary shifts and extensions to regular shifts and to schedule and assign tasks. In the second phase, a column-generation heuristic embedded in a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.

关键词： Personnel scheduling Work shifts Activity and task assignment Flexible scheduling Overtime Temporary employees mixed-integer programming Column generation

来源：评论

学校读者我要写书评

暂无评论

Optimal placement of reconfigurable optical add/drop multiplexers with packing, blocking, and signal loss

引用

COMPUTER NETWORKS 2013年第6期57卷 1443-1458页

作者： Borraz-Sanchez, Conrado Klabjan, Diego Northwestern Univ Inst Technol Dept Ind Engn & Management Sci Evanston IL 60208 USA

With technological and manufacturing advances, and increased economies of scale, today the use of Reconfigurable Optical Add/Drop Multiplexers (ROADMs) has become economical. A ROADM allows individual or multiple wavelengths to be added and/or dropped from a transport fiber without the need to convert the signals to electrical and back again to optical. This feature makes a fiber optic network more flexible, i.e., the network can be remotely configured/reconfigured through ROADMs. Consequently, due to high capital cost, to determine an optimal placement of ROADMs and to assign wavelengths in a cost efficient way becomes an important problem in network topology design. We introduce a mixed integer programming model that captures signal loss and wavelength packing/blocking, and develop a three-phase algorithm to efficiently solve it. Analytical justifications for the algorithmic steps are provided. Computational experiments are conducted to assess the tractability of the model, and to evaluate the performance of the proposed approach. The execution times of the algorithm are acceptable. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Add/drop multiplexer placement ROADM WDM network mixed-integer programming Wavelength packing/blocking

来源：评论

学校读者我要写书评

暂无评论

A robust optimization model for multi-product two-stage capacitated production planning under uncertainty

引用

APPLIED MATHEMATICAL MODELLING 2013年第20-21期37卷 8957-8971页

作者： Rahmani, Donya Ramezanian, Reza Fattahi, Parviz Heydari, Mandi Iran Univ Sci & Technol Dept Ind Engn Tehran Iran Bu Ali Sina Univ Dept Ind Engn Hamadan Iran

Production planning (PP) is one of the most important issues carried out in manufacturing environments which seeks efficient planning, scheduling and coordination of all production activities that optimizes the company's objectives. In this paper, we studied a two-stage real world capacitated production system with lead time and setup decisions in which some parameters such as production costs and customer demand are uncertain. A robust optimization model is developed to formulate the problem in which minimization of the total costs including the setup costs, production costs, labor costs, inventory costs, and workforce changing costs is considered as performance measure. The robust approach is used to reduce the effects of fluctuations of the uncertain parameters with regards to all the possible future scenarios. A mixed-integer programming (MIP) model is developed to formulate the related robust production planning problem. In fact the robust proposed model is presented to generate an initial robust schedule. The performance of this schedule could be improved against of any possible occurrences of uncertain parameters. A case from an Iran refrigerator factory is studied and the characteristics of factory and its products are discussed. The computational results display the robustness and effectiveness of the model and highlight the importance of using robust optimization approach in generating more robust production plans in the uncertain environments. The tradeoff between solution robustness and model robustness is also analyzed. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Production planning Uncertainty Robust optimization mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：