The stochastic bid generation problem in combinatorial transportation auctions

In this paper, we deal with the generation of bundles of loads to be submitted by carriers participating in combinatorial auctions in the context of long-haul full truckload transportation services. We develop a probabilistic optimization model that integrates the bid generation and pricing problems together with the routing of the carrier’s fleet. We propose two heuristic procedures that enable us to solve models with up to 400 auctioned loads.     

A clustering approach for scenario tree reduction: an application to a stochastic programming portfolio optimization problem

This paper deals with the problem of scenario tree reduction for stochastic programming problems. In particular, a reduction method based on cluster analysis is proposed and tested on a portfolio optimization problem. Extensive computational experiments were carried out to evaluate the performance of the proposed approach, both in terms of computational efficiency and efficacy. The analysis of the results shows that the clustering approach exhibits good performance also when compared with other reduction approaches.     

Water distribution networks design under uncertainty

Water distribution networks are important systems that provide citizens with an essential public service which is crucial for the normal development of most basic activities of life. Despite many water distribution network problems have been extensively investigated in the literature, the presence of uncertainty in the data has often been neglected. This paper studies the challenging problem of designing an isolation system for water distribution networks under different failure scenarios. To solve the problem, three heuristic methods are presented and analyzed on a real case study taken from the literature. Numerical results show the merits of the suggested techniques for solving the problem.     

An exact approach for solving integer problems under probabilistic constraints with random technology matrix

This paper addresses integer programming problems under probabilistic constraints involving discrete distributions. Such problems can be reformulated as large scale integer problems with knapsack constraints. For their solution we propose a specialized Branch and Bound approach where the feasible solutions of the knapsack constraint are used as partitioning rules of the feasible domain. The numerical experience carried out on a set covering problem with random covering matrix shows the validity of the solution approach and the efficiency of the implemented algorithm.     

The Express heuristic for probabilistically constrained integer problems

Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic constraints which assure the satisfaction of the stochastic constraints with a given probability, whereas the second one is due to the integer nature of the decision variables. In this paper we present a tailored heuristic approach based on alternating phases of exploration and feasibility repairing which we call Express (Explore and Repair Stochastic Solution) heuristic. The exploration is carried out by the iterative solution of simplified reduced integer problems in which probabilistic constraints are discarded and deterministic additional constraints are adjoined. Feasibility is restored through a penalty approach. Computational results, collected on a probabilistically constrained version of the classical 0–1 multiknapsack problem, show that the proposed heuristic is able to determine good quality solutions in a limited amount of time.     

Sequencing 5‐Hydroxymethyluracil at Single‐Base Resolution

5‐hydroxymethyluracil (5hmU) is formed through oxidation of thymine both enzymatically and non‐enzymatically in various biological systems. Although 5hmU has been reported to affect biological processes such as protein–DNA interactions, the consequences of 5hmU formation in genomes have not been yet fully explored. Herein, we report a method to sequence 5hmU at single‐base resolution. We employ chemical oxidation to transform 5hmU to 5‐formyluracil (5fU), followed by the polymerase extension to induce T‐to‐C base changes owing to the inherent ability of 5fU to form 5fU:G base pairing. In combination with the Illumina next generation sequencing technology, we developed polymerase chain reaction (PCR) conditions to amplify the T‐to‐C base changes and demonstrate the method in three different synthetic oligonucleotide models as well as part of the genome of a 5hmU‐rich eukaryotic pathogen. Our method has the potential capability to map 5hmU in genomic DNA and thus will contribute to promote the understanding of this modified base.     

Efficient Parallel Algorithms for the Minimum Cost Flow Problem

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the -relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the -relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.     

Fix and Relax Heuristic for a Stochastic Lot-Sizing Problem

This paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the problem. The computational experiments carried out on a large set of instances have shown that the approach provides good quality solutions in a reasonable amount of time.     

Parallel Algorithms for Solving the Convex Minimum Cost Flow Problem

In this paper we deal with the solution of the separable convex cost network flow problem. In particular, we propose a parallel asynchronous version of the -relaxation method and we prove theoretically its correctness.We present two implementations of the parallel method for a shared memory multiprocessor system, and we empirically analyze their numerical performance on different test problems. The preliminary numerical results show a good reduction of the execution time of the parallel algorithm with the respect to the sequential counterpart.     

Balancing efficiency and equity in location-allocation models with an application to strategic EMS design

This paper presents an integrated location-allocation model balancing efficiency and equity criteria. The new formulation combines two domains: facility location and data envelopment analysis. To support the decision maker with more realistic solutions based on the optimal location-allocation decisions, we endogenize the outputs of the model as a function dependent on the allocation variables. To illustrate the viability of the proposed approach, we investigated the potential application of the model to the design of an emergency medical service system.