A note on “a dual-ascent approach to the fixed-charge capacitated network design problem”

We show by a counterexample that the dual-ascent procedure proposed by Herrmann, Ioannou, Minis and Proth in a 1996 issue of the European Journal of Operational Research is incorrect in the sense that it does not generate a valid lower bound to the optimal value of fixed-charge capacitated network design problems. We provide a correct dual-ascent procedure based on the same ideas and we give an interpretation of it in terms of a simple Lagrangean relaxation. Although correct, this procedure is not effective, as in general, it provides a less tighter bound than the linear programming relaxation.     

A large neighbourhood search approach to the multi-activity shift scheduling problem

The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities.     

A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.     

A bilinear approach to the pooling problem†

In this paper we present an algorithm for the pooling problem in refinery optimization based on a bilinear programming approach. The pooling problem occurs frequently in process optimization problems, especially refinery planning models. The main difficulty is that pooling causes an inherent nonlinearity in the otherwise linear models. We shall define the problem by formulating an aggregate mathematical model of a refinery, comment on solution methods for pooling problems that have been presented in the literature, and develop a new method based on convex approximations of the bilinear terms. The method is illustrated on numerical examples     

On a parallel genetic–tabu search based algorithm for solving the graph colouring problem

In this paper, we are interested in a particular combinatorial optimisation problem (COP), namely the graph colouring problem (GCP). To solve the GCP, we present a parallel approach adopting an efficient strategy. A brief survey on known methods for solving the GCP enables us to justify our approach which is based on a hybrid method, starting from a set of solutions initialized by the so-called RLF colouring method and combining both a genetic algorithm and the tabu search. A parallelising strategy is then applied. The performances of our method were evaluated through a series of experimentations achieved on an IBM SP2 multiprocessor. The processed graphs were chosen from two benchmark sets. The first, taken from the Internet, involves graphs whose chromatic numbers are known and the second involves random generated graphs. The analysis of the results proves the interest of our approach.     

A Boolean satisfiability approach to the resource-constrained project scheduling problem

We formulate the resource-constrained project scheduling problem as a satisfiability problem and adapt a satisfiability solver for the specific domain of the problem. Our solver is lightweight and shows good performance both in finding feasible solutions and in proving lower bounds. Our numerical tests allowed us to close several benchmark instances of the RCPSP that have never been closed before by proving tighter lower bounds and by finding better feasible solutions. Using our method we solve optimally more instances of medium and large size from the benchmark library PSPLIB and do it faster compared to any other existing solver.     

A hybrid constraint programming approach to?the?log-truck scheduling problem

Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. This paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. The problem consists of scheduling the transportation of logs between forest areas and woodmills, as well as routing the fleet of vehicles to satisfy these transportation requests. The objective is to minimize the total cost of the non-productive activities such as the waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integer programming model to deal with the optimization of deadheads. Both of these models are combined through the exchange of global constraints. Finally the whole approach is validated on real industrial data.     

All roads lead to Rome—New search methods for the optimal triangulation problem

To perform efficient inference in Bayesian networks by means of a Junction Tree method, the network graph needs to be triangulated. The quality of this triangulation largely determines the efficiency of the subsequent inference, but the triangulation problem is unfortunately NP-hard. It is common for existing methods to use the treewidth criterion for optimality of a triangulation. However, this criterion may lead to a somewhat harder inference problem than the total table size criterion. We therefore investigate new methods for depth-first search and best-first search for finding optimal total table size triangulations. The search methods are made faster by efficient dynamic maintenance of the cliques of a graph. This problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix’ approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. The algorithms for finding optimal triangulations are mainly supposed to be off-line methods, but they may form the basis for efficient any-time heuristics. Furthermore, the methods make it possible to evaluate the quality of heuristics precisely and allow us to discover parts of the search space that are most important to direct randomized sampling to.     

A Hybrid Taguchi–Immune approach to optimize an integrated supply chain design problem with multiple shipping

Supply chain network design is considered a strategic decision level problem that provides an optimal platform for the effective and efficient supply chain management. In this research, we have mathematically modeled an integrated supply chain design. To ensure high customer service levels, we propose the inclusion of multiple shipping/transportation options and distributed customer demands with fixed lead times into the supply chain distribution framework and formulated an integer-programming model for the five-tier supply chain design problem considered. The problem has been made additionally complex by including realistic assumptions of nonlinear transportation and inventory holding costs and the presence of economies of scale. In the light of aforementioned facts, this research proposes a novel solution methodology that amalgamates the features of Taguchi technique with Artificial Immune System (AIS) for the optimum or near optimum resolution of the problem at hand. The performance of the proposed solution methodology has been benchmarked against a set of test instances and the obtained results are compared against those obtained by Genetic Algorithm (GA), Hybrid Taguchi–Genetic Algorithm (HTGA) and AIS. Simulation results indicate that the proposed approach can not only search for optimal/near optimal solutions in large search spaces but also has good repeatability and convergence characteristics, thereby proving its superiority.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

A filter-and-fan approach to the 2D HP model of?the?protein folding problem

We examine a prominent and widely-studied model of the protein folding problem, the two-dimensional (2D) HP model, by means of a filter-and-fan (F&F) solution approach. Our method is designed to generate compound moves that explore the solution space in a dynamic and adaptive fashion. Computational results for standard sets of benchmark problems show that the F&F algorithm is highly competitive with the current leading algorithms, requiring only a single solution trial to obtain best known solutions to all problems tested, in contrast to a hundred or more trials required in the typical case to evaluate the performance of the best of the alternative methods.     

A viscosity approach to the Dirichlet problem for complex Monge–Ampère equations

We present a viscosity approach to the Dirichlet problem for the complex Monge–Ampère equation ${\det u_{\bar{j} k} = f (x, u)}$ . Our approach differs from previous viscosity approaches to this equation in several ways: it is based on contact set techniques (the Alexandrov–Bakelman–Pucci estimate), on extensive applications of sup-inf convolutions, and on a relation between real and complex Hessians. More specifically, this paper includes a notion of viscosity solutions; a comparison principle and a solvability theorem; the equivalence between viscosity and pluripotential solutions; an estimate of the modulus of continuity of a solution in terms of that of a given subsolution and of the right-hand side f; and an Alexandrov–Bakelman–Pucci type of L ^∞-estimate.     

Existence of solutions to the Riemann problem for 2 × 2 conservation laws

We consider the Riemann problem for a class of 2?×?2 systems of conservation laws which do not satisfy the strictly hyperbolicity condition. Our main assumption is that the product of non-diagonal elements within the F?echet derivative (Jacobian) of the flux is nonnegative. By improving a vanishing viscosity approach, we establish the existence of solutions to the Riemann problem for those systems.     

A subjective Bayesian approach to the theory of queues I — Modeling

This is the first of an expository two-part paper which outlines a point of view different from that currently used in queueing theory. In both parts, the focus is on concepts. Here we adopt a personal probability point of view to all sources of uncertainty in the theory of queues and explore the consequences of our approach by comparing our results to those that are currently available. For ease of exposition, we confine attention to the M/M/1/ and the M/M/1/K queues. In Part I we outline the general strategy and focus on model development. In Part II we address the problem of inference in queues within the subjective Bayesian paradigm and introduce a use of Shannon's measure of information for assessing the amount of information conveyed by the various types of data from queues.