A unified exact method for solving different classes of vehicle routing problems

This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Problem (SDVRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). This paper presents an exact algorithm for the HVRP based on the set partitioning formulation. The exact algorithm uses three types of bounding procedures based on the LP-relaxation and on the Lagrangean relaxation of the mathematical formulation. The bounding procedures allow to reduce the number of variables of the formulation so that the resulting problem can be solved by an integer linear programming solver. Extensive computational results over the main instances from the literature of the different variants of HVRPs, SDVRP and MDVRP show that the proposed lower bound is superior to the ones presented in the literature and that the exact algorithm can solve, for the first time ever, several test instances of all problem types considered.      

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

Constrained control for uncertain linear systems

The linear state feedback synthesis problem for uncertain linear systems with state and control constraints is considered. We assume that the uncertainties are present in both the state and input matrices and they are bounded. The main goal is to find a linear control law assuring that both state and input constraints are fulfilled at each time. The problem is solved by confining the state within a compact and convex positively invariant set contained in the allowable state region.It is shown that, if the controls, the state, and the uncertainties are subject to linear inequality constraints and if a candidate compact and convex polyhedral set is assigned, a feedback matrix assuring that this region is positively invariant for the closed-loop system is found as a solution of a set of linear inequalities for both continuous and discrete time design problems.These results are extended to the case in which additive disturbances are present. The relationship between positive invariance and system stability is investigated and conditions for the existence of positively invariant regions of the polyhedral type are given.The author is grateful to Drs. Vito Cerone and Roberto Tempo for their comments.     

A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

This article introduces a new exact algorithm for the capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSD can be formulated as a set partitioning problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme. Computational experiments show promising results.     

The biaxial Fueter theorem

This paper deals with a special type of solutions for the Dirac operator on ? ^m , which can be obtained through a biaxial generalisation of the classical Fueter Theorem. This is a result which allows to generate zonal solutions for the Dirac equation starting from arbitrary holomorphic functions in the complex plane. Invoking operator identities for Jacobi polynomials, it is shown how this procedure can be extended to more general splittings than the one usually considered in the literature.     

Bi-matrix Games with Fuzzy Goals and Fuzzy

A bi-matrix game with fuzzy goal is shown to be equivalent to a (crisp) non-linear programming problem in which the objective as well as all constraint functions are linear except two constraint functions, which are quadratic. This equivalence is further extended to bi-matrix games with fuzzy pay-offs, as well as to bi-matrix games with fuzzy goals and fuzzy payoffs, whose equilibrium strategies are conceptualized by employing a suitable ranking (defuzzification) function.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

Extended Global Convergence Framework for Unconstrained Optimization

An extension of the global convergence framework for unconstrained derivative-free optimization methods is presented. The extension makes it possible for the framework to include optimization methods with varying cardinality of the ordered direction set. Grid-based search methods are shown to be a special case of the more general extended global convergence framework. Furthermore,the required properties of the sequence of ordered direction sets listed in the definition of grid-based methods are relaxed and simplified by removing the requirement of structural equivalence.     

Numerical experiments with variations of the Gauss-Newton algorithm for nonlinear least squares

In this paper, the classical Gauss-Newton method for the unconstrained least squares problem is modified by introducing a quasi-Newton approximation to the second-order term of the Hessian. Various quasi-Newton formulas are considered, and numerical experiments show that most of them are more efficient on large residual problems than the Gauss-Newton method and a general purpose minimization algorithm based upon the BFGS formula. A particular quasi-Newton formula is shown numerically to be superior. Further improvements are obtained by using a line search that exploits the special form of the function.     

Linear programming approach to the control of discrete-time periodic systems with uncertain inputs

The problem is considered of finding a control strategy for a linear discrete-time periodic system with state and control bounds in the presence of unknown disturbances that are only known to belong to a given compact set. This kind of problem arises in practice in resource distribution systems where the demand has typically a periodic behavior, but cannot be estimated a priori without an uncertainty margin. An infinite-horizon keeping problem is formulated, which consists in confining the state within its constraint set using the allowable control, whatever the allowed disturbances may be. To face this problem, the concepts of periodically invariant set and sequence are introduced. They are used to formulate a solution strategy that solves the keeping problem. For the case of polyhedral state, control, and disturbance constraints, a computationally feasible procedure is proposed. In particular, it is shown that periodically invariant sequences may be computed off-line, and then they may be used to synthesize on-line a control strategy. Finally, an optimization criterion for the control law is discussed.     

Descent methods for convex essentially smooth minimization

Consider the problem of minimizing a convex essentially smooth function over a polyhedral set. For the special case where the cost function is strictly convex, we propose a feasible descent method for this problem that chooses the descent directions from a finite set of vectors. When the polyhedral set is the nonnegative orthant or the entire space, this method reduces to a coordinate descent method which, when applied to certain dual of linearly constrained convex programs with strictly convex essentially smooth costs, contains as special cases a number of well-known dual methods for quadratic and entropy (either –logx orx logx) optimization. Moreover, convergence of these dual methods can be inferred from a general convergence result for the feasible descent method. When the cost function is not strictly convex, we propose an extension of the feasible descent method which makes descent along the elementary vectors of a certain subspace associated with the polyhedral set. The elementary vectors are not stored, but generated using the dual rectification algorithm of Rockafellar. By introducing an -complementary slackness mechanism, we show that this extended method terminates finitely with a solution whose cost is within an order of of the optimal cost. Because it uses the dual rectification algorithm, this method can exploit the combinatorial structure of the polyhedral set and is well suited for problems with a special (e.g., network) structure.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058.     

The Solution of Massive Generalized Set Partitioning Problems in Aircrew Rostering

The scheduling and rostering of personnel is a problem that occurs in many organizations. Aircrew scheduling has attracted considerable attention with many heuristic methods being proposed, but in recent times set partitioning optimization methods have become more popular. The aircrew rostering problem is discussed and formulated as a generalized set partitioning model. Because of the extremely large optimization models that are generated in practical situations, some special computational techniques have been developed to produce solutions efficiently. These techniques are used to solve problems arising from an airline application in which set partitioning models with more than 650 constraints and 200 000 binary variables are generated. The solutions are produced on a Motorola 68020 microprocessor in little more than three hours.     

Optimizing single-terminal dispatch of large volume trips to trucks

In this paper, we consider the problem of delivering large volumes of products from a single supplier to a set of commercial outlets with the use of a non-homogeneous fleet of trucks. The non-homogeneity implies different costs and, hence, traditional methods which measure miles, hours, and/or number of trucks are not appropriate. The problem may be modeled as an elastic generalized assignment problem. A special purpose branch and bound algorithm is developed and a set of real-world distribution problems and solved.     

Two-dimensional homogeneous cubic systems: Classification and normal forms. I

This work is the first in a series of papers devoted to classifying of two-dimensional homogeneous cubic systems based on partitioning into classes of linear equivalence. Principles have been developed that are capable of constructively distinguishing the structure of a simplest system in each class and a canonical set that defines the admissible values that can be assumed by its coefficients. The polynomial vector in the right-hand part of this system identified with a 2 × 4 matrix is called the canonical form (CF) and the system itself is called the normal cubic form. One of the main objectives of this series of papers is to maximally simplify the reduction of a system with a homogeneous cubic polynomial in the unperturbed part to the various structures of a generalized normal form (GNF). Generalized normal form refers to a system in which the perturbed part has the simplest form in some sense. The constructive implementation of the normalization process depends on the ability to explicitly specify the conditions of compatibility and possible solutions of the so-called bonding system, which is understood to be a countable set of linear algebraic equations that specify the normalizing transformations of the perturbed system. The above principles are based on the idea of the maximum possible simplification of the bonding system. This will allow one to first reduce the initial perturbed system by an invertible linear substitution of variables to a system with some CF in the unperturbed part, then reduce the resulting system, which is optimal for normalization, by almost identical substitutions to various structures of the GNF. In this paper, the following tasks are carried out: (1) the general problem is set, close problems are formulated, and the available results are described; (2) a bonding system is derived that is capable of determining the equivalence of any two perturbed systems with the same homogeneous cubic part, the possibilities of its simplification are discussed, the GNF is defined, and the method of resonant equations is given allowing one to constructively obtain all its structures; (3) special forms of recording homogeneous cubic systems in the presence of a common homogeneous factor in their right-hand parts with a degree of 1–3 are introduced, and the linear equivalence of these systems, as well as of systems without a common factor is studied, and key linear invariants are offered.     

All-integer column generation for set partitioning: Basic principles and extensions

Column generation, combined with an appropriate integer programming technique, has shown to be a powerful tool for solving huge integer programmes arising in various applications. In these column generation approaches, the master problem is often of a set partitioning type.     

Lot-sizing with production and delivery time windows

We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs. For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Fixed charge problems with identical fixed charges

The general problem considered by this paper is a special case of the fixed-charge problem. The further condition imposed is that all variables have the same associated fixed-charge. The problem is discussed in the context of a known commercial application, that being the cutting stock problem. The situation considered is that of cutting given numbers of small rectangles from large rectangular stock-plates. In many such situations major aims are to have low stock-plate usage and a low number of setups of the cutting equipment. These represent conflicting objectives capable of being combined by the use of fixed charges upon the setups but this paper presents an alternative approach incorporating direct manipulation of the number of setups involved in the solution. This approach is compared to a solution technique for the general fixed-charge problem.     

New lower bounds for the facility location problem with clients’ preferences

A bilevel facility location problem in which the clients choose suppliers based on their own preferences is studied. It is shown that the coopertative and anticooperative statements can be reduced to a particular case in which every client has a linear preference order on the set of facilities to be opened. For this case, various reductions of the bilevel problem to integer linear programs are considered. A new statement of the problem is proposed that is based on a family of valid inequalities that are related to the problem on a pair of matrices and the set packing problem. It is shown that this formulation is stronger than the other known formulations from the viewpoint of the linear relaxation and the integrality gap.