An object-oriented methodology for solving the RCPSPs with heuristics and metaheuristics

Because various heuristics and metaheuristics have been proposed to solve the well known NP-hard, resourceconstrained project scheduling problem (RCPSP), it is currently difficult to compare the computational efficiency of these heuristics implemented on different computers where, in addition, the computer codes may have been written in different computer languages. This problem is solved when all relevant heuristics can be applied within the framework of a single computer program. By use of the object-oriented programming (OOP) methodology, we developed a general software framework for the heuristics and metaheuristics for solving the RCPSP. Currently this includes six heuristics and two metaheuristics. The framework of the software allows a more advanced user to append more effective heuristics and play around with several parameters of these metaheuristics with a bare minimum of coding effort.     

A Strategic,Area-wide Contingency Planning Model for Oil Spill Cleanup Operations with Application Demonstrated to the Galveston Bay Area*

This paper develops a general integer programming model for strategic, area-wide contingency planning of oil spill cleanup operations. Model inputs include the set of risk points and the likely spill scenarios and response requirements for each, the sites of existing storage locations and the inventory of components at each, and potential sites for new storage locations. The model prescribes a minimum total cost plan to either build new storage locations, expand existing ones, or both, to purchase new components and pre-position them, and a contingency plan that determines which response systems should be composed to enable an effective time-phased response for each likely spill scenario. A family of heuristics based on linear programming (LP) is devised to resolve this strategic problem, providing an area-wide contingency plan. The heuristics are evaluated on a set of 10 test problems that involve 1869 general integer variables and 3264 constraints. Computational tests indicate that four heuristics are quite effective, prescribing solutions for each of 10 test cases within 1.41% of optimum and within a few minutes runtime. This study focused on modeling the Galveston Bay Area, and the test problems represent application in that area. A sensitivity analysis is demonstrated by assessing the impacts of component availability and the degradation of cleanup capability over time. Use of the model as a decision support aid by responsible parties, contractors, governmental organizations and others is described.     

Solving Spreadsheet-Based Integer Programming Models: An Example from International Telecommunications

Considerable effort has recently been devoted to augmenting existing spreadsheet capabilities with the power of mathematical programming. One way to accomplish this is to design mathematical programming-based solution methodologies (most likely heuristics) that exploit existing spreadsheet capabilities. We describe how this latter approach was successfully applied to an integer programming model of an international telecommunications network.     

A Lagrangian relaxation approach for the multiple sequence alignment problem

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.     

废弃物回收的多层逆向物流网络优化设计问题研究

废弃物逆向物流网络设计问题是一个关系到经济效益和社会效益的问题.本文研究了废弃物逆向物流网络设计问题,包括选择中转站和处理站的地址,确定将产生点的废弃物分配给中转站以及从中转站运送到处理站的最佳策略,确定处理站的容量.考虑了在满足公众的意愿的情况下,建立了一个多目标的纯整数规划模型,最小化总的建设费用和设施对公众产生的负效用.设计了基于启发式的两阶段分解算法求解,从而构建一个废弃物回收的多层逆向物流网络.最后的算例仿真表明了算法的有效性和可行性.     

Heuristics for the network design problem with connectivity requirements

We consider the NP-complete problem of finding a spanning \(k\)-tree of minimum weight in a complete weighted graph. This problem has a number of applications in designing reliable backbone telecommunication networks. We propose effective algorithms based on a greedy strategy and several variable neighborhood search metaheuristics. We also develop an integer linear programming model for calculating a lower bound. Preliminary numerical experiments using random and real-word data sets are reported to show the effectiveness of our approach. In addition, we compare our approach with known metaheuristics.     

SCHEDULING PARALLEL PROCESSORS WITH SETUP COSTS AND RESOURCE LIMITATIONS

An integer linear programming model is presented for the scheduling of n products on m identical machines. The particular problem studied is one that occurs frequently in the fiberglass and textile industries. The model incorporates setup costs, lost production costs, and overtime costs. Due to the structure of the model, integer solutions can be obtained by explicitly restricting only a small number of the integer variables. This allows those responsible for scheduling to solve realistically sized problems in an efficient manner. Computational results are provided for a set of generated test problems.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

An Application of the AXIS Solution Framework to Multiple Objective Aggregate Production Planning

This paper provides data on the first application of a prototype of the AXIS solution framework. AXIS (algorithms combined with knowledge systems in an interactive sequence) is a framework for interactively combining structured algorithms that seek a best solution with knowledge-based expert systems that seek expert heuristic solutions. This paper tests the framework using an interactive multiple objective integer programming algorithm combined with heuristics taken from the domain of aggregate production planning. The results indicate the AXIS framework can be successful in generating high quality solutions, in vastly reduced solution times compared to the structured algorithms, at much lower costs compared to the expert heuristics working alone.     

考虑定价和需求关系的供应链网络优化研究

本文通过引入价格-需求函数描述产品价格变化对消费者需求的影响，构建了一个由制造商、仓库和消费者组成的三级供应链网络。在此基础上，以最大化供应链总利润为目标、以定价和需求为决策变量，建立了混合整数非线性规划（MINLP）模型。基于该模型目标函数非线性的复杂性，采用外部近似法将目标函数近似线性化，即切割成有限条切线，使其可以求解。最后通过不同规模的算例分析验证了模型和算法的可行性与有效性，从而指导供应链上的企业权衡其成本和收益，提高顾客的满意度。     

MODELING LEARNING CURVE AND LEARNING COMPLEMENTARITY FOR RESOURCE ALLOCATION AND PRODUCTION SCHEDULING*

Research on learning effects in mathematical programming models for optimum resource allocation has called attention to the difficulty in solving such models in their original nonlinear form. In this paper, systematically varying sizes of linear segments are designed to approximate productivity changes along the learning curve, and a single separable linear programming model is developed. With production complementarity and learning transmission between products, a more realistic resource allocation and production scheduling problem emerges. Two cases of learning transmissions are considered, and the model design process, which defines a decision problem that can be solved by a simplex algorithm, is demonstrated.     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

On cutting stock with due dates

Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances.     

The Retail Planning Problem Under Demand Uncertainty

We consider the retail planning problem in which the retailer chooses suppliers and determines the production, distribution, and inventory planning for products with uncertain demand to minimize total expected costs. This problem is often faced by large retail chains that carry private‐label products. We formulate this problem as a convex‐mixed integer program and show that it is strongly NP‐hard. We determine a lower bound by applying a Lagrangian relaxation and show that this bound outperforms the standard convex programming relaxation while being computationally efficient. We also establish a worst‐case error bound for the Lagrangian relaxation. We then develop heuristics to generate feasible solutions. Our computational results indicate that our convex programming heuristic yields feasible solutions that are close to optimal with an average suboptimality gap at 3.4%. We also develop managerial insights for practitioners who choose suppliers and make production, distribution, and inventory decisions in the supply chain.     

Attacking the Market Split Problem with Lattice Point Enumeration

The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.     

A branch-and-price approach for trip sequence planning of high-speed train units

In high-speed railway operations, a trip sequence plan is made once the timetable is determined, and serves as a reference in the subsequent operations of train units scheduling. In light of the maintenance requirements of train units and periodicity characteristics of trip sequences, we introduce a trip sequence graph to describe the train units’ movement and coupling/splitting in a railway network. Based on the trip sequence graph, two integer linear programming models are then formulated, namely a path-based model and an arc-based model. Integrated with the characteristics of the trip sequence graph, a customized branch-and-price algorithm is developed to solve the path-based model. The two models are applied to the high-speed railway network in eastern China, and through numerical experiments, the effectiveness and applicability of the models are discussed.     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

多目标物流网络优化模型的研究

针对物流网络规划中需要考虑多个目标的问题,以配流中心存储容量及使用率为约束,建立了基于总费用及最大单程距离(费用)最小的双目标数学模型,给出了优化模型的求解方法,为决策者提供多种可供选择的优化方案。     

PORTFOLIO MODELING IN MULTIPLE-CRITERIA SITUATIONS UNDER UNCERTAINTY: COMMENT

In a recent issue of Decision Sciences, Muhlemann, Lockett, and Gear [8] developed a multiple-objective, stochastic linear programming formulation of the multiperiod portfolio selection problem under uncertainty. The purpose of this note is to offer some extensions to their multicriteria approach which is otherwise viewed as an excellent attempt at modeling realistic aspects of the portfolio selection problem. Further, integer goal programming combined with simulation is suggested as an alternate approach for solving the dynamic multiple-objective problem.