Algorithms for railway crew management

Crew management is concerned with building the work schedules of crews needed to cover a planned timetable. This is a well-known problem in Operations Research and has been historically associated with airlines and mass-transit companies. More recently, railway applications have also come on the scene, especially in Europe. In practice, the overall crew management problem is decomposed into two subproblems, called crew scheduling and crew rostering. In this paper, we give an outline of different ways of modeling the two subproblems and possible solution methods. Two main solution approaches are illustrated for real-world applications. In particular we discuss in some detail the solution techniques currently adopted at the Italian railway company, Ferrovie dello Stato SpA, for solving crew scheduling and rostering problems.     

Optimal dividend-equity issuance strategy in a dual model with fixed and proportional transaction costs

In this paper, we consider the problem of optimal dividend payout and equity issuance for a company whose liquid asset is modeled by the dual of classical risk model with diffusion. We assume that there exist both proportional and fixed transaction costs when issuing new equity. Our objective is to maximize the expected cumulative present value of the dividend payout minus the equity issuance until the time of bankruptcy,which is defined as the first time when the company’s capital reserve falls below zero. The solution to the mixed impulse-singular control problem relies on two auxiliary subproblems: one is the classical dividend problem without equity issuance, and the other one assumes that the company never goes bankrupt by equity issuance.We first provide closed-form expressions of the value functions and the optimal strategies for both auxiliary subproblems. We then identify the solution to the original problem with either of the auxiliary problems. Our results show that the optimal strategy should either allow for bankruptcy or keep the company’s reserve above zero by issuing new equity, depending on the model’s parameters. We also present some economic interpretations and sensitivity analysis for our results by theoretical analysis and numerical examples.     

A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

Discrete location for bundled demand points

This paper considers a discrete location problem where the demand points are grouped. We propose a formulation, an enforcement for it, and an associated Lagrangian relaxation, and then we build feasible solutions to the problem from the optimal solutions to the relaxed subproblems. Valid inequalities for the formulation are also identified and added to the set of relaxed constraints. This method produces good feasible solutions and enables us to address large instances of the problem. Computational experiments have been performed with benchmark instances from the literature on related problems.     

One-parametric bottleneck transportation problems

We discuss the bottleneck transportation problem with one nonlinear parameter in the bottleneck objective function. A finite sequence of feasible basic solutions which are optimal in subsequent closed parameter-intervals is generated using a primal method for the nonparametric subproblems. The best among three primal codes for solving these subproblems is selected on extensive computational comparisons. We discuss computational experience with the sequential method for the case of linear and quadratic dependence on one parameter. Observed computational behaviour is O((n ·m)), with 2.     

Constructing a course schedule by solving a series of assignment type problems

We propose in this paper a new approach for tackling constrained course scheduling problems. The main idea is to decompose the problem into a series of easier subproblems. Each subproblem is an assignment type problem in which items have to be assigned to resources subject to some constraints. By solving a first series of assignment type subproblems, we build an initial solution which takes into account the constraints imposing a structure on the schedule. The total number of overlapping situations is reduced in a second phase by means of another series of assignment type problems. The proposed approach was implemented in practice and has proven to be satisfactory.     

Parallel Variable Distribution for Constrained Optimization

In the parallel variable distribution framework for solving optimization problems (PVD), the variables are distributed among parallel processors with each processor having the primary responsibility for updating its block of variables while allowing the remaining secondary variables to change in a restricted fashion along some easily computable directions. For constrained nonlinear programs convergence theory for PVD algorithms was previously available only for the case of convex feasible set. Additionally, one either had to assume that constraints are block-separable, or to use exact projected gradient directions for the change of secondary variables. In this paper, we propose two new variants of PVD for the constrained case. Without assuming convexity of constraints, but assuming block-separable structure, we show that PVD subproblems can be solved inexactly by solving their quadratic programming approximations. This extends PVD to nonconvex (separable) feasible sets, and provides a constructive practical way of solving the parallel subproblems. For inseparable constraints, but assuming convexity, we develop a PVD method based on suitable approximate projected gradient directions. The approximation criterion is based on a certain error bound result, and it is readily implementable. Using such approximate directions may be especially useful when the projection operation is computationally expensive.     

Algorithm robust for the bicriteria discrete optimization problem

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.     

A modified nearly exact method for solving low-rank trust region subproblem

In this paper, we first discuss how the nearly exact (NE) method proposed by Moré and Sorensen [14] for solving trust region (TR) subproblems can be modified to solve large-scale “low-rank” TR subproblems efficiently. Our modified algorithm completely avoids computation of Cholesky factorizations by instead relying primarily on the Sherman–Morrison–Woodbury formula for computing inverses of “diagonal plus low-rank” type matrices. We also implement a specific version of the modified log-barrier (MLB) algorithm proposed by Polyak [17] where the generated log-barrier subproblems are solved by a trust region method. The corresponding direction finding TR subproblems are of the low-rank type and are then solved by our modified NE method. We finally discuss the computational results of our implementation of the MLB method and its comparison with a version of LANCELOT [5] based on a collection extracted from CUTEr [12] of nonlinear programming problems with simple bound constraints.      

Nonadditive Shortest Paths: Subproblems in Multi-Agent Competitive Network Models

A variety of different multi-agent (competitive) network models have been described in the literature. Computational techniques for solving such models often involve the iterative solution of shortest path subproblems. Unfortunately, the most theoretically interesting models involve nonlinear cost or utility functions and they give rise to nonadditive shortest path subproblems. This paper both describes some basic existence and uniqueness results for these subproblems and develops a heuristic for solving them.     

Auxiliary problem principle and decomposition of optimization problems

The auxiliary problem principle allows one to find the solution of a problem (minimization problem, saddle-point problem, etc.) by solving a sequence of auxiliary problems. There is a wide range of possible choices for these problems, so that one can give special features to them in order to make them easier to solve. We introduced this principle in Ref. 1 and showed its relevance to decomposing a problem into subproblems and to coordinating the subproblems. Here, we derive several basic or abstract algorithms, already given in Ref. 1, and we study their convergence properties in the framework of i infinite-dimensional convex programming.     

Approximations in proximal bundle methods and decomposition of convex programs

A proximal bundle method is presented for minimizing a nonsmooth convex functionf. At each iteration, it requires only one approximate evaluation off and its -subgradient, and it finds a search direction via quadratic programming. When applied to the Lagrangian decomposition of convex programs, it allows for inexact solutions of decomposed subproblems; yet, increasing their required accuracy automatically, it asymptotically finds both the primal and dual solutions. It is an implementable approximate version of the proximal point algorithm. Some encouraging numerical experience is reported.The author thanks two anonymous referees for their valuable comments.Research supported by the State Committee for Scientific Research under Grant 8550502206.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

Penalty Algorithms in Hilbert Spaces

We analyze the classical penalty algorithm for nonlinear programming in Hilbert spaces and obtain global convergence results, as well as asymptotic superlinear convergence order. These convergence results generalize similar results obtained for finite-dimensional problems. Moreover, the nature of the algorithms allows us to solve the unconstrained subproblems in finite-dimensional spaces.     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

Adjustable Robust Optimization Models for a Nonlinear Two-Period System

We study two-period nonlinear optimization problems whose parameters are uncertain. We assume that uncertain parameters are revealed in stages and model them using the adjustable robust optimization approach. For problems with polytopic uncertainty, we show that quasiconvexity of the optimal value function of certain subproblems is sufficient for the reducibility of the resulting robust optimization problem to a single-level deterministic problem. We relate this sufficient condition to the cone-quasiconvexity of the feasible set mapping for adjustable variables and present several examples and applications satisfying these conditions. This work was partially supported by the National Science Foundation, Grants CCR-9875559 and DMS-0139911, and by Grant-in-Aid for Scientific Research from the Ministry of Education, Sports, Science and Culture of Japan, Grant 16710110.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Plant location with minimum inventory

We present an integer programming model for plant location with inventory costs. The linear programming relaxation has been solved by Dantzig-Wolfe decomposition. In this case the subproblems reduce to the minimum cut problem. We have used subgradient optimization to accelerate the convergence of the D-W algorithm. We present our experience with problems arising in the design of a distribution network for computer spare parts. In most cases, from a fractional solution we were able to derive integer solutions within 4% of optimality.     

Smoothed penalty algorithms for optimization of nonlinear models

We introduce an algorithm for solving nonlinear optimization problems with general equality and box constraints. The proposed algorithm is based on smoothing of the exact l ₁-penalty function and solving the resulting problem by any box-constraint optimization method. We introduce a general algorithm and present theoretical results for updating the penalty and smoothing parameter. We apply the algorithm to optimization problems for nonlinear traffic network models and report on numerical results for a variety of network problems and different solvers for the subproblems.     

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.