Linear programming models with planned lead times for supply chain operations planning

This paper contributes to the development of models for capacity constrained Supply Chain Operations Planning (SCOP). We focus on production environments with arbitrary supply chain structures. The demand for the end items is assumed to be exogenously determined. We solve the SCOP problem with Linear Programming models using planned lead times with multi-period capacity consumption. Using planned lead times increases the reliability of the communication between SCOP and Scheduling with regard to the feasibility of the planning. Planned lead times also reduce the nervousness in the system. We model capacity constraints on the quantity of items that can be assembled within a time interval. In particular, items can be assigned to multiple resources. We discuss two LP approaches which plan the production of items so that a sum of inventory costs and costs due to backordering is minimized.     

An aggregate stochastic programming model for air traffic flow management

In this paper, we present an aggregate mathematical model for air traffic flow management (ATFM), a problem of great concern both in Europe and in the United States. The model extends previous approaches by simultaneously taking into account three important issues: (i) the model explicitly incorporates uncertainty in the airport capacities; (ii) it also considers the trade-off between airport arrivals and departures, which is a crucial issue in any hub airport; and (iii) it takes into account the interactions between different hubs.The level of aggregation proposed for the mathematical model allows us to solve realistic size instances with a commercial solver on a PC. Moreover it allows us to compute solutions which are perfectly consistent with the Collaborative Decision-Making (CDM) procedure in ATFM, widely adopted in the USA and which is currently receiving a lot of attention in Europe. In fact, the proposed model suggests the number of flights that should be delayed, a decision that belongs to the ATFM Authority, rather than assigning delays to individual aircraft.     

Re-solving stochastic programming models for airline revenue management

We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi-stage stochastic programming formulation to the seat allocation problem. Our theoretical results show that the proposed approximation is robust, in the sense that solving more successive two-stage programs can never worsen the expected revenue obtained with the corresponding allocation policy. Although intuitive, such a property is known not to hold for the traditional deterministic linear programming model found in the literature. We also show that this property does not hold for some bid-price policies. In addition, we propose a heuristic method to choose the re-solving points, rather than re-solving at equally-spaced times as customary. Numerical results are presented to illustrate the effectiveness of the proposed approach.     

Mathematical programming models for revenue management under customer choice

We study a network airline revenue management problem with discrete customer choice behavior. We discuss a choice model based on the concept of preference orders, in which customers can be grouped according to a list of options in decreasing order of preference. If a customer’s preferred option is not available, the customer moves to the next choice on the list with some probability. If that option is not available, the customer moves to the third choice on the list with some probability, and so forth until either the customer has no other choice but to leave or his/her request is accepted. Using this choice model as an input, we propose some mathematical programs to determine seat allocations. We also propose a post-optimization heuristic to refine the allocation suggested by the optimization model. Simulation results are presented to illustrate the effectiveness of our method, including comparisons with other models.     

Bilevel programming in traffic planning: Models,methods and challenge

Well-founded traffic models recognize the individual network user's right to the decision as to when, where and how to travel. On the other hand, the decisions concerning management, control, design and improvement investments are made by the public sector in the interest of the society as a whole. Hence, transportation planning is a characteristic example of a hierarchical process, in which the public sector at one level makes decisions seeking to improve the performance of the network, while at another level the network users make choices with regard to route, travel mode, origin and destination of their travel. Our objective is to provide a review on the current state of research and development in bilevel programming problems that arize in this context, and attract the attention of the global optimization community to this problem class of imense practical importance.     

A fuzzy-robust stochastic multiobjective programming approach for petroleum waste management planning

This paper proposes a fuzzy-robust stochastic multiobjective programming (FRSMOP) approach, which integrates fuzzy-robust linear programming and stochastic linear programming into a general multiobjective programming framework. A chosen number of noninferior solutions can be generated for reflecting the decision-makers’ preferences and subjectivity. The FRSMOP method can effectively deal with the uncertainties in the parameters expressed as fuzzy membership functions and probability distribution. The robustness of the optimization processes and solutions can be significantly enhanced through dimensional enlargement of the fuzzy constraints. The developed FRSMOP was then applied to a case study of planning petroleum waste-flow-allocation options and managing the related activities in an integrated petroleum waste management system under uncertainty. Two objectives are considered: minimization of system cost and minimization of waste flows directly to landfill. Lower waste flows directly to landfill would lead to higher system costs due to high transportation and operational costs for recycling and incinerating facilities, while higher waste flows directly to landfill corresponding to lower system costs could not meet waste diversion objective environmentally. The results indicate that uncertainties and complexities can be effectively reflected, and useful information can be generated for providing decision support.     

Scenario generation and stochastic programming models for asset liability management

In this paper, we develop and test scenario generation methods for asset liability management models. We propose a multi-stage stochastic programming model for a Dutch pension fund. Both randomly sampled event trees and event trees fitting the mean and the covariance of the return distribution are used for generating the coefficients of the stochastic program. In order to investigate the performance of the model and the scenario generation procedures we conduct rolling horizon simulations. The average cost and the risk of the stochastic programming policy are compared to the results of a simple fixed mix model. We compare the average switching behavior of the optimal investment policies. Our results show that the performance of the multi-stage stochastic program could be improved drastically by choosing an appropriate scenario generation method.     

Survey of mathematical programming models in air pollution management

This paper surveys the current state of the literature in management science/operations research approaches to air pollution management. After introducing suitable background we provide some of the institutional and legal framework needed to understand the continuing regulatory efforts in United States. Attention is then turned to mathematical programming models ranging from fairly simple deterministic linear programs to quite sophisticated stochastic models which have appeared in the literature dealing with these topics. This is followed by extensions reflecting some of the work we have undertaken in association with the Texas Natural Resource Conservation Commission, a regulatory agency in Texas. Application and potential use of models is the central theme of this survey. Issues for future research are presented at the end and an extensive list of publications is provided in the references at the end of the article.Principal air quality issues of local, national, and international concern are listed below in increasing order of difficulty based on the number of different types of pollutants and problems in quantification of the risks the pollutants pose:

• 1.1. Stratospheric ozone depletion: one relatively easily controllable class of trace gases - ozone depleting chemicals, or ODCs, principally chloroflurocarbons (CFCs) — with relatively well quantified risks;
• 2.2. Criteria pollutants: six common pollutants — ozone (O₃), carbon monoxide (CO), sulfur dioxide (SO₂), nitrogen dioxide (NO₂), lead (Pb), and particulate matter less than 10 microns in size (PM10) — regulated since 1970 in the U.S. and presenting relatively well quantified risks;
• 3.3. Acid precipitation: two relatively easily controllable classes of trace gases — oxides of nitrogen (NO_x) and oxides of sulfur (SO_x) with relatively well quantified risks;
• 4.4. Global warming/climate change: a few difficult to control trace gases — principally carbon dioxide (CO₂), methane (CH₄), nitrous oxide (N₂O), and CFCs — with highly uncertain risks;
• 5.5. Toxics or HAPS (hazardous air pollutants): hundreds of types of gaseous chemicals and particles with uncertain risks;
• 6.6. Somewhat dated, but nevertheless useful, is the following reference: Glossary on Air Pollution (Copenhagen, World Health Organization, 1980).

     

Probabilistic models for medical insurance claims

The paper develops two probabilistic models for claim size in health insurance based on the claims of families and individuals covered by the policy. First, general models for the numbers of families and persons covered by a medical insurance are developed. These are then used to construct models for claim size. Applications of these general models are then analysed and discussed. Copyright © 2007 John Wiley & Sons, Ltd.     

Stochastic models for air cargo terminal manpower supply planning in long‐term operations

In this research, based on two deterministic‐demand planning models, we established two long‐term stochastic‐demand planning models by incorporating the stochastic disturbances of manpower demands that occur in actual operations. The models are formulated as mixed integer linear programs that are solved using a mathematical programming solver. To compare the performance of the two stochastic‐demand and two deterministic‐demand planning models under the stochastic demands that occur in actual operations, we further develop a simulation‐based evaluation method. Finally, we perform numerical tests using real operating data from a Taiwan air cargo terminal. The preliminary results show that the stochastic models could be useful for planning air cargo terminal manpower supply. Copyright © 2008 John Wiley & Sons, Ltd.     

A traffic shaping model for optimizing network operations

The management of technology in multi-service computer networks, such as university networks, has become a challenge with the explosive growth of entertainment oriented peer-to-peer (P2P) traffic. Traffic shaping is one of the tools used to manage bandwidth to improve system performance by allocating bandwidth between P2P and non-peer-to-peer (NP2P) traffic. We present a model for traffic shaping and bandwidth management that considers the trade-offs from allocating different amounts of bandwidths for different application categories and use data from a university network. The current policy allocates varying bandwidths over the day to P2P and NP2P traffic to reflect the importance of not letting entertainment based traffic choke the network during the day time at the expense of the more important traffic, such as Web traffic. We highlight the difficulties in obtaining data in the form required for analysis, and the need to estimate demand for allocations not covered by current policy. We present a goal programming model for this estimation task. We also model the traffic shaping problem as a Markov decision process and develop an algorithm for determining the optimal bandwidth allocation to maximize the utility of all users. Finally we use a numerical example to illustrate our approach.     

Discrete-time dynamic traffic assignment models with periodic planning horizon: system optimum

This paper proposes a system optimal dynamic traffic assignment model that does not require the network to be empty at the beginning or at the end of the planning horizon. The model assumes that link travel times depend on traffic densities and uses a discretized planning horizon. The resulting formulation is a nonlinear program with binary variables and a time-expanded network structure. Under a relatively mild condition, the nonlinear program has a feasible solution. When necessary, constraints can be added to ensure that the solution satisfies the First-In-First-Out condition. Also included are approximation schemes based on linear integer programs that can provide solutions arbitrarily close to that of the original nonlinear problem.     

Probabilistic analysis of a differential equation for linear programming

In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find the surprising result that the distribution of the convergence rate is a scaling function of a single variable. This scaling variable combines the convergence rate with the problem size (i.e., the number of variables and the number of constraints). We also estimate numerically the distribution of the computation time to an approximate solution, which is the time required to reach a vicinity of the attracting fixed point. We find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times to the approximate solution.     

A two-stage fuzzy robust integer programming approach for capacity planning of environmental management systems

In this study, a two-stage fuzzy robust integer programming (TFRIP) method has been developed for planning environmental management systems under uncertainty. This approach integrates techniques of robust programming and two-stage stochastic programming within a mixed integer linear programming framework. It can facilitate dynamic analysis of capacity-expansion planning for waste management facilities within a multi-stage context. In the modeling formulation, uncertainties can be presented in terms of both possibilistic and probabilistic distributions, such that robustness of the optimization process could be enhanced. In its solution process, the fuzzy decision space is delimited into a more robust one by specifying the uncertainties through dimensional enlargement of the original fuzzy constraints. The TFRIP method is applied to a case study of long-term waste-management planning under uncertainty. The generated solutions for continuous and binary variables can provide desired waste-flow-allocation and capacity-expansion plans with a minimized system cost and a maximized system feasibility.     

Mixed-integer programming models for nesting problems

Several industrial problems involve placing objects into a container without overlap, with the goal of minimizing a certain objective function. These problems arise in many industrial fields such as apparel manufacturing, sheet metal layout, shoe manufacturing, VLSI layout, furniture layout, etc., and are known by a variety of names: layout, packing, nesting, loading, placement, marker making, etc. When the 2-dimensional objects to be packed are non-rectangular the problem is known as the nesting problem. The nesting problem is strongly NP-hard. Furthermore, the geometrical aspects of this problem make it really hard to solve in practice. In this paper we describe a Mixed-Integer Programming (MIP) model for the nesting problem based on an earlier proposal of Daniels, Li and Milenkovic, and analyze it computationally. We also introduce a new MIP model for a subproblem arising in the construction of nesting solutions, called the multiple containment problem, and show its potentials in finding improved solutions.     

Probabilistic abductive logic programming using Dirichlet priors

Probabilistic programming is an area of research that aims to develop general inference algorithms for probabilistic models expressed as probabilistic programs whose execution corresponds to inferring the parameters of those models. In this paper, we introduce a probabilistic programming language (PPL) based on abductive logic programming for performing inference in probabilistic models involving categorical distributions with Dirichlet priors. We encode these models as abductive logic programs enriched with probabilistic definitions and queries, and show how to execute and compile them to boolean formulas. Using the latter, we perform generalized inference using one of two proposed Markov Chain Monte Carlo (MCMC) sampling algorithms: an adaptation of uncollapsed Gibbs sampling from related work and a novel collapsed Gibbs sampling (CGS). We show that CGS converges faster than the uncollapsed version on a latent Dirichlet allocation (LDA) task using synthetic data. On similar data, we compare our PPL with LDA-specific algorithms and other PPLs. We find that all methods, except one, perform similarly and that the more expressive the PPL, the slower it is. We illustrate applications of our PPL on real data in two variants of LDA models (Seed and Cluster LDA), and in the repeated insertion model (RIM). In the latter, our PPL yields similar conclusions to inference with EM for Mallows models.     

Integrating operations research in constraint programming

This paper presents constraint programming (CP) as a natural formalism for modelling problems, and as a flexible platform for solving them. CP has a range of techniques for handling constraints including several forms of propagation and tailored algorithms for global constraints. It also allows linear programming to be combined with propagation and novel and varied search techniques which can be easily expressed in CP. The paper describes how CP can be used to exploit linear programming within different kinds of hybrid algorithm. In particular it can enhance techniques such as Lagrangian relaxation, Benders decomposition and column generation.     

An optimization approach for planning daily drayage operations

Daily drayage operations involve moving loaded or empty equipment between customer locations and rail ramps. Our goal is to minimize the cost of daily drayage operations in a region on a given day. Drayage orders are generally pickup and delivery requests with time windows. The repositioning of empty equipment may also be required in order to facilitate loaded movements. The drayage orders are satisfied by a heterogeneous fleet of drivers. Driver routes must satisfy various operational constraints. We present an optimization methodology for finding cost-effective schedules for regional daily drayage operations. The core of the formulation is a set partitioning model whose columns represent routes. Routes are added to the formulation by column generation. We present numerical results for real-world data which demonstrate that our methodology produces low cost solutions in a reasonably short time.     

数学规划与约束规划整合下的多目标分组排序问题研究

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在 三者之间进行权衡. 多目标分组排序问题 的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解 效率.