A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.     

A global optimization approach for solving three-dimensional open dimension rectangular packing problems

The three-dimensional open dimension rectangular packing problem (3D-ODRPP) aims to pack a set of given rectangular boxes into a large rectangular container of minimal volume. This problem is an important issue in the shipping and moving industries. All the boxes can be any rectangular stackable objects with different sizes and may be freely rotated. The 3D-ODRPP is usually formulated as a mixed-integer non-linear programming problem. Most existing packing optimization methods cannot guarantee to find a globally optimal solution or are computationally inefficient. Therefore, this paper proposes an efficient global optimization method that transforms a 3D-ODRPP as a mixed-integer linear program using fewer extra 0–1 variables and constraints compared to existing deterministic approaches. The reformulated model can be solved to obtain a global optimum. Experimental results demonstrate the computational efficiency of the proposed approach in globally solving 3D-ODRPPs drawn from the literature and the practical applications.     

A moment matching approach to log-normal portfolio optimization

We consider the problem where a manager aims to minimize the probability of his portfolio return falling below a threshold while keeping the expected return no worse than a target, under the assumption that stock returns are Log-Normally distributed. This assumption, common in the finance literature for daily and weekly returns, creates computational difficulties because the distribution of the portfolio return is difficult to estimate precisely. We approximate it with a single Log-Normal random variable using the Fenton–Wilkinson method and investigate an iterative, data-driven approximation to the problem. We propose a two-stage solution approach, where the first stage requires solving a classic mean-variance optimization model and the second step involves solving an unconstrained nonlinear problem with a smooth objective function. We suggest an iterative calibration method to improve the accuracy of the method and test its performance against a Generalized Pareto Distribution approximation. We also extend our results to the design of basket options.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法

传统的求解0-1规划问题方法大多属于直接离散的解法.现提出一个包含严格转换和近似逼近三个步骤的连续化解法:(1)借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量;(2)对目标函数采用逼近折中阶跃函数近光滑打磨函数,约束条件采用线性打磨函数逼近折中阶跃函数,把0-1规划问题由离散问题转化为连续优化模型;(3)利用高阶光滑的解法求解优化模型.该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例,使求解0-1规划问题的方法更加一般化.在具体求解时,采用正弦型光滑打磨函数来逼近折中阶跃函数,计算效果很好.     

Tuning a parametric Clarke–Wright heuristic via a genetic algorithm

Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

Towards a unified territorial design approach — Applications, algorithms and GIS integration

Territory design may be viewed as the problem of grouping small geographic areas into larger geographic clusters called territories in such a way that the latter are acceptable according to relevant planning criteria. In this paper we review the existing literature for applications of territory design problems and solution approaches for solving these types of problems. After identifying features common to all applications we introduce a basic territory design model and present in detail two approaches for solving this model: a classical location-allocation approach combined with optimal split resolution techniques and a newly developed computational geometry based method. We present computational results indicating the efficiency and suitability of the latter method for solving large-scale practical problems in an interactive environment. Furthermore, we discuss extensions to the basic model and its integration into Geographic Information Systems.     

On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty

We present a model for optimizing a mean-risk function of the terminal wealth for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. Some logical constraints are considered to be satisfied by the assets portfolio. Uncertainty is represented by a scenario tree and is dealt with by a multistage stochastic mixed 0-1 model with complete recourse. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. A Branch-and-Fix Coordination approach for the multistage 0–1 program solving is proposed. Some computational experience is reported.      

A new computational approach for solving optimal control of linear PDEs problem

In this paper, we present a new computational approach for solving an internal optimal control problem, which is governed by a linear parabolic partial differential equation. Our approach is to approximate the PDE problem by a nonhomogeneous ordinary differential equation system in higher dimension. Then, the homogeneous part of ODES is solved using semigroup theory. In the next step, the convergence of this approach is verified by means of Toeplitz matrix. In the rest of the paper, the optimal control problem is solved by utilizing the solution of homogeneous part. Finally, a numerical example is given.     

Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods

The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.     

Solving (large scale) matching problems combinatorially

In this paper we describe computational results for a modification of the shortest augmenting path approach for solving large scale matching problems. Using a new assignment start procedure and the two-phase strategy, where first the problem is solved on a sparse subgraph and then reoptimization is used, matching problems on complete graphs with 1000 nodes are solved in about 10–15 seconds on an IBM 4361.This work was partially supported by Sonderforschungsbereich 303, University of Bonn, and a special grant from the Deutsche Forschungsgemeinschaft.     

An efficient deterministic optimization approach for rectangular packing problems

The rectangular packing problem aims to seek the best way of placing a given set of rectangular pieces within a large rectangle of minimal area. Such a problem is often constructed as a quadratic mixed-integer program. To find the global optimum of a rectangular packing problem, this study transforms the original problem as a mixed-integer linear programming problem by logarithmic transformations and an efficient piecewise linearization approach that uses a number of binary variables and constraints logarithmic in the number of piecewise line segments. The reformulated problem can be solved to obtain an optimal solution within a tolerable error. Numerical examples demonstrate the computational efficiency of the proposed method in globally solving rectangular packing problems.     

Using genetic algorithm to solve dynamic cell formation problem

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed using genetic algorithm (GA). Previous models presented in the literature contain some essential errors which will decline their advantageous aspects. In this paper these errors are discussed and a new improved formulation for dynamic cell formation (DCF) problem is presented. Due to the fact that CF is a NP-hard problem, solving the model using classical optimization methods needs a long computational time. Therefore the improved DCF model is solved using a proposed GA and the results are compared with the optimal solution and the efficiency of the proposed algorithm is discussed and verified.     

Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm

When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Manpower allocation using genetic annealing

In this paper, we focus on a real size manpower allocation problem. It was modeled after a real world problem of distributing the salesmen force over the branches of a company. The problem includes multiple objectives and the number of salesmen at each branch is unspecified. Conventional integer programming approach and conventional metaheuristics seem to have problems with solving the large size version of this problem. The versatility of our proposed heuristics based on a modification of genetic annealing is exemplified through solving the real size manpower allocation problem. For comparison sake, several small sized versions were solved using our method, conventional integer programming approach, and some well known metaheuristics.     

A relation between the output regulation and the observer design for nonlinear systems

Output regulation and observer design are two important problems for nonlinear systems, and there is a vast literature addressing each problem separately in the control literature. Isidori and Byrnes [1] have solved the output regulation problem for nonlinear systems with a Poisson stable exosystem, and Sundarapandian [2] has solved the exponential observer design problem for Lyapunov stable nonlinear systems. In this paper, we demonstrate that for a special class of Lyapunov stable nonlinear systems, namely neutrally stable systems, the exponential observer design problem can be solved by converting it into an output regulation problem and then solving the new problem using the output regulation techniques of Isidori and Byrnes [1]. Finally, we present the corresponding results for the discrete-time case.     

A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs

The focus of this paper is on finding optimal solutions for the problem of maximal partitioning of graphs with supply and demand (MPGSD) for arbitrary graphs. A mixed integer programming (MIP) model is developed for the problem of interest. We also present some specific constraints that can be used in the case of tree graphs. With the goal of lowering the computational cost for solving the underlying model, a preprocessing stage is included. It is used to produce additional constraints based on shortest paths in the graph. With the aim of exploring the effectiveness of the proposed MIP formulation we have performed computational experiments for general graphs and trees. The main objective of the tests is to observe the properties and sizes of supply/demand graphs that can be solved to optimality using the proposed approach in reasonable time. The conducted computational experiments have shown that the proposed method is especially suitable for sparse graphs.