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

Computer-assisted proof of performance ratios for the Differencing Method

DISCRETE OPTIMIZATION 2012年第1期9卷 1-16页

作者： Michiels, W. Aarts, E. Korst, J. van Leeuwen, J. Spieksma, F. C. R. Philips Res Labs NL-5656 AA Eindhoven Netherlands Univ Utrecht NL-3508 TB Utrecht Netherlands KULeuven B-3000 Louvain Belgium

We consider the problem of partitioning a set of n numbers into m subsets of cardinality k = [n/m] or [n/m ], such that the maximum subset sum is minimal. We show that the performance ratio of the Differencing Method of Karmarkar and Karp for solving this problem is at least 2 - Sigma(k-01)(i=0) ll/kl for any fixed k. We also build a mixed integer linear programming model (MILP) whose solution yields the performance ratio for any given k. For k <= 7 these MILP-instances can be solved with an exact MILP-solver. This results in a computer-assisted proof of the tightness of the aforementioned lower bound for k <= 7. For k > 7 we prove that 2 - 1/k-1 is an upper bound on the performance ratio, thereby leaving a gap with the lower bound of Theta(k-3), which is less than 0.4%. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Differencing Method Balanced number partitioning Worst-case performance Computer-assisted proof mixed integer linear programming Exact LP solver

来源：评论

学校读者我要写书评

暂无评论

PAMSCOD: Platoon-based arterial multi-modal signal control with online data

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2012年第1期20卷 164-184页

作者： He, Qing Head, K. Larry Ding, Jun Univ Arizona Tucson AZ 85721 USA

A unified platoon-based mathematical formulation called PAMSCOD is presented to perform arterial (network) traffic signal control while considering multiple travel modes in a vehicle-to-infrastructure communications environment. First, a headway-based platoon recognition algorithm is developed to identify pseudo-platoons given probe vehicles' online information. It is assumed that passenger vehicles constitute a significant majority of the vehicles in the network. This algorithm identifies existing queues and significant platoons approaching each intersection. Second, a mixed-integer linear program (MILP) is solved to determine future optimal signal plans based on the current traffic controller status, online platoon data and priority requests from special vehicles such as transit buses. Deviating from the traditional common network cycle length, PAMSCOD aims to provide multi-modal dynamical progression (MDP) on the arterial based on the probe information. Microscopic simulation using VISSIM shows that PAMSCOD can easily handle two common traffic modes, transit buses and automobiles, and significantly reduce delays for both modes under both non-saturated and oversaturated traffic conditions as compared to traditional state-of-practice coordinated-actuated signal control with timings optimized by SYNCHRO. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Multi-modal traffic signal control Platoon recognition mixed integer linear programming Multi-modal dynamical progression Vehicle-to-infrastructure communications

来源：评论

学校读者我要写书评

暂无评论

A new linear programming approach and genetic algorithm for solving airline boarding problem

引用

APPLIED MATHEMATICAL MODELLING 2012年第9期36卷 4060-4072页

作者： Soolaki, Majid Mahdavi, Iraj Mandavi-Amiri, Nezam Hassanzadeh, Reza Aghajani, Aydin Mazandaran Univ Sci & Technol Dept Ind Engn Babol Sar *** Iran Sharif Univ Technol Fac Math Sci Tehran Iran Allameh Mohaddes Noori Inst Dept Ind Engn Noor Iran

The airline industry is under intense competition to simultaneously increase efficiency and satisfaction for passengers and profitability and internal system benefit for itself. The boarding process is one way to achieve these objectives as it tends itself to adaptive changes. In order to increase the flying time of a plane, commercial airlines try to minimize the boarding time, which is one of the most lengthy parts of a plane's turn time. To reduce boarding time, it is thus necessary to minimize the number of interferences between passengers by controlling the order in which they get onto the plane through a boarding policy. Here, we determine the passenger boarding problem and examine the different kinds of passenger boarding strategies and boarding interferences in a single aisle aircraft. We offer a new integer linear programming approach to reduce the passenger boarding time. A genetic algorithm is used to solve this problem. Numerical results show effectiveness of the proposed algorithm. (C) 2011 Elsevier Inc. All rights reserved.

关键词： OR in airlines mixed integer linear programming Transportation Boarding strategy Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Path Planning for UAVs Under Communication Constraints Using SPLAT! and MILP

引用

JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS 2012年第1-4期65卷 265-282页

作者： Grotli, Esten Ingar Johansen, Tor Arne Dept Engn Cybernet N-7491 Trondheim Norway

We will in this paper address the problem of offline path planning for Unmanned Aerial Vehicles (UAVs). Our goal is to find paths that meet mission objectives, are safe with respect to collision and grounding, fuel efficient and satisfy criteria for communication. Due to the many nonconvex constraints of the problem, mixed integer linear programming (MILP) will be used in finding the path. Approximate communication constraints and terrain avoidance constraints are used in the MILP formulation. To achieve more accurate prediction of the ability to communicate, the path is then analyzed in the radio propagation toolbox SPLAT!, and if the UAVs are not able to communicate according to design criteria for bandwidth, constraints are modified in the optimization problem in an iterative manner. The approach is exemplified with the following setup: The path of two UAVs are planned so they can serve as relay nodes between a target without line of sight to the base station.

关键词： Path planning mixed integer linear programming Communication constraints Unmanned aerial vehicles

来源：评论

学校读者我要写书评

暂无评论

Inverse optimization with endogenous arrival time constraints to calibrate the household activity pattern problem

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2012年第3期46卷 463-479页

作者： Chow, Joseph Y. J. Recker, Will W. Univ Calif Irvine Inst Transportat Studies Irvine CA 92697 USA

A parameter estimation method is proposed for calibrating the household activity pattern problem so that it can be used as a disaggregate, activity-based analog of the traffic assignment problem for activity-based travel forecasting. Inverse optimization is proposed for estimating parameters of the household activity pattern problem such that the observed behavior is optimal, the patterns can be replicated, and the distribution of the parameters is consistent. In order to fit the model to both the sequencing of activities and the arrival times to those activities, an inverse problem is formulated as a mixed integer linear programming problem such that coefficients of the objectives are jointly estimated along with the goal arrival times to the activities. The formulation is designed to be structurally similar to the equivalent problems defined by Ahuja and Orlin and can be solved exactly with a cutting plane algorithm. The concept of a unique invariant common prior is used to regularize the estimation method, and proven to converge using the Method of Successive Averages. The inverse model is tested on sample households from the 2001 California Household Travel Survey and results indicate a significant improvement over the standard inverse problem in the literature as well as baseline prescriptive models that do not make use of sample data for calibration. Although, not unexpectedly, the estimated optimization model by itself is a relatively poor forecasting model, it may be used in determining responses of a population to spatio-temporal scenarios where revealed preference data is absent. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Inverse optimization Activity based mixed integer linear programming Pickup and delivery problem Goal programming Common prior

来源：评论

学校读者我要写书评

暂无评论

Rescheduling of elective patients upon the arrival of emergency patients

引用

DECISION SUPPORT SYSTEMS 2012年第1期54卷 551-563页

作者： Erdem, Ergin Qu, Xiuli Shi, Jing N Dakota State Univ Dept Ind & Mfg Engn Fargo ND 58108 USA N Carolina Agr & Tech State Univ Dept Ind & Syst Engn Greensboro NC 27411 USA

In this study, a mixed integer linear programming (MILP) model is developed for rescheduling elective patients upon the arrival of emergency patients by considering two types of clinical units, namely operating rooms and post-anesthesia care units (PACUs). The model considers the overtime cost of the operating rooms and/or the PACUs, the cost of postponing or preponing elective surgeries, and the cost of turning down the emergency patients. The results indicate that a mainstream commercial solver can efficiently find an optimal solution in a particular scenario with light elective surgery load, but becomes very inefficient in searching optimal solutions in all other scenarios. As such, a genetic algorithm is developed to efficiently obtain the approximately optimal solutions in those scenarios that are difficult for the commercial solver. In the genetic algorithm, a novel chromosome structure is proposed and applied to represent the feasible solutions to the MILP model. It is shown that for the scenarios with heavy load of elective surgeries, the genetic algorithm can find approximate optimal solutions significantly faster than the commercial solver. In practice, the two solution methodologies should be used jointly to provide hospitals a solid tool for making sound and timely decisions in admitting emergency patients and rescheduling elective patients. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Elective surgery Rescheduling Emergency admission Operating room mixed integer linear programming Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A dynamic model to optimize a regional energy system with waste and crops as energy resources for greenhouse gases mitigation

引用

ENERGY 2012年第1期46卷 522-532页

作者： Song, Han Dotzauer, Erik Thorin, Eva Guziana, Bozena Huopana, Tuomas Yan, Jinyue Malardalen Univ Sch Sustainable Dev Soc & Technol SE-72123 Vasteras Sweden Univ Eastern Finland Dept Environm Sci Kuopio 70211 Finland Royal Inst Technol Sch Chem Sci & Engn SE-10044 Stockholm Sweden

A dynamic model of a regional energy system has been developed to support sustainable waste treatment with greenhouse gases (GHG) mitigation, addressing the possibility for development towards a regional fossil fuel-free society between 2011 and 2030. The model is based on conventional mixed integer linear programming (MILP) techniques to minimize the total cost of regional energy systems. The CO2 emission component in the developed model includes both fossil and biogenic origins when considering waste, fossil fuels and other renewable sources for energy production. A case study for the county of Vastmanland in central Sweden is performed to demonstrate the applicability of the developed MILP model in five distinct scenarios. The results show significant potential for mitigating CO2 emission by gradually replacing fossil fuels with different renewable energy sources. The MILP model can be useful for providing strategies for treating wastes sustainably and mitigating GHG emissions in a regional energy system, which can function as decision bases for formulating GHG reduction policies and assessing the associated economic implications. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Waste Regional energy system Dynamic mixed integer linear programming Fossil-fuel-free Sustainable

来源：评论

学校读者我要写书评

暂无评论

Methods for multi-objective investment and operating optimization of complex energy systems

引用

ENERGY 2012年第1期45卷 12-22页

作者： Fazlollahi, Samira Mandel, Pierre Becker, Gwenaelle Marechal, Francois VERI F-78520 Limay France Ecole Polytech Fed Lausanne IGM STI LENIStn 9 CH-1015 Lausanne Switzerland

The design and operations of energy systems are key issues for matching energy supply and consumption. Several optimization methods based on the mixed integer linear programming (MILP) have been developed for this purpose. However, due to uncertainty of some parameters like market conditions and resource availability, analyzing only one optimal solution with mono objective function is not sufficient for sizing the energy system. In this study, a multi-period energy system optimization (ESO) model with a mono objective function is first explained. The model is then developed in a multi-objective optimization perspective to systematically generate a good set of solutions by using integer cut constraints (ICC) algorithm and epsilon constraint. These two methods are discussed and compared. In the next step, the ESO model is reformulated as a multi-objective optimization model with an evolutionary algorithm (EMOO). In this step the model is decomposed into master and slave optimization. Finally developed models are demonstrated by means of a case study comprising six types of conversion technologies, namely, a heat pump, boiler, photovoltaics, as well as a gas turbine, fuel cell and gas engine. Results show that, EMOO is particularly suited for multi-objective optimizations, working with a population of potential solutions, each presenting a different trade-off between objectives. However, MILP with ICC and epsilon constraint is more suited for generating a small set of ordered solutions with shorter resolution time. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Energy systems mixed integer linear programming Evolutionary algorithm Multi-objective optimization CO2 mitigation integer cut constraints (ICC)

来源：评论

学校读者我要写书评

暂无评论

Use of flux pre-analysis to enable ¹³C tracer studies in pyruvate kinase-deficient Escherichia coli

引用

BIOTECHNOLOGY JOURNAL 2012年第3期7卷 449-462页

作者： Meade, Jonathan Khan, Saleem Ataai, Mohammad Domach, Michael Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA Univ Pittsburgh Dept Microbiol & Mol Genet Pittsburgh PA USA Univ Pittsburgh Dept Chem & Petr Engn Pittsburgh PA 15261 USA

Pyruvate kinase-deficient Escherichia coli (PB25) is a low by-product-producing yet fast-growing mutant that has been shown to have technological potential. Determining the flux limits through finding the extreme point flux sets was previously reported to identify alternate metabolite trafficking scenarios. Previously, the extreme point flux sets were used to design tracer experiments;however, variation in extracellular measurements was not considered, and reaction reversibility was assumed to be low to moderate. In this study, we examined the utility of limiting the fluxes and predetermining the trafficking scenarios in PB25, including confirmation of quasi-linearity between extreme points to ensure sensitivity is maintained. The effects of variation in extracellular measurements and reaction reversibilities were also examined. Tightened flux limits reduced the nonlinearity between label distribution and fluxes. For low to moderate reversibility, contrast was also preserved. However, for highly reversible phosphoglucoisomerase activity, information from common analytes could lead to a flux solution that is biased towards one extreme point. Based on the PB25 model, some suggestions are provided for how predetermining flux limits and trafficking scenarios could enable flux identification in larger network problems.

关键词： C-13 metabolic flux analysis Escherichia coli Flux limits mixed integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Oil production optimization solved by piecewise linearization in a Branch & Price framework

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第11期39卷 2469-2477页

作者： Gunnerud, V. Foss, B. A. McKinnon, K. I. M. Nygreen, B. Norwegian Univ Sci & Technol Dept Engn Cybernet N-7491 Trondheim Norway Norwegian Univ Sci & Technol Dept Ind Econ & Technol Management N-7491 Trondheim Norway Univ Edinburgh Sch Math Edinburgh EH9 3JZ Midlothian Scotland

This paper presents a method for optimizing oil production on large scale production networks such as the Troll west field in the North Sea. The method is based on piecewise linearization of all nonlinearities, and on decomposition of the full scale problem into smaller subproblems. Column generation in a Branch & Price framework is used to solve the decomposed problem. The method differs from most Branch & Price methods by branching only on continuous quantities and by solving the subproblems using commercial MILP software. The method is applied to a realistic model of an oil field, the Troll oil and gas field at the Norwegian Continental Shelf, a petroleum asset with severe production optimization challenges due to rate dependent gas-coning wells. This study shows that the method is capable of solving instances of practical size to proven optimality. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Oil production planning Oil rim reservoir mixed integer linear programming Column generation Branch & Price

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：