Search

Two-stage stochastic decision problems are characterized by the property that in stage one part of the decision has to be made before relevant data are observed and the rest of the decision can be made in stage two after data are available. It is generally assumed that while the data missing in stage one are not known, their probability distribution is known. In this paper, we consider a special form of such problems where the objective function is quadratic in the first and second stage decisions and the goal is to minimize the expected quadratic cost function. We assume that the decisions must lie in a standard simplex, but do not require convexity of the uncertain objective. It is well known that such quadratic optimization programs are NP-complete and thus belong to the most complex optimization problems. A viable method to attack such problems is to find bounds for the original complicated problem by solving easier approximate problems. We describe such approximations and show that by exploiting their properties, good but not necessarily optimal solutions can be found. We also present possible applications, such as selecting invited speakers for conferences with the aim to generate a community with high coherence. Finally, systematic numerical results are provided.

In this paper, we derive deterministic inner approximations for single and joint independent or dependent probabilistic constraints based on classical inequalities from probability theory such as the one-sided Chebyshev inequality, Bernstein inequality, Chernoff inequality and Hoeffding inequality (see Pinter, 1989). The dependent case has been modelled via copulas. New assumptions under which the bounds based approximations are convex allowing to solve the problem efficiently are derived. When the convexity condition can not hold, an efficient sequential convex approximation approach is further proposed to solve the approximated problem. Piecewise linear and tangent approximations are also provided for Chernoff and Hoeffding inequalities allowing to reduce the computational complexity of the associated optimization problem. Extensive numerical results on a blend planning problem under uncertainty are finally provided allowing to compare the proposed bounds with the Second Order Cone (SOCP) formulation and Sample Average Approximation (SAA).

We study a fixed-charge transportation problem under stochastic and dynamic demand. We propose a multi-stage mixed integer stochastic programming formulation, where the first-stage decision is the delivery from the supplier to the retailers, while transshipment is used, in addition to classical backordering as recourse decision. The objective is the minimization of the total expected cost. We prove that this problem is NP-hard and, through a worst-case analysis, that transshipment can provide significant cost savings. Extensive computational studies are carried out to evaluate the performance of a rolling horizon approach with respect to the optimal cost. Numerical results show that this heuristic provides effective solutions in short computational time. Managerial insights are finally drawn.

We address a long–haul transportation problem of delivering a set of products from a producer to a customer, where Full Container Load (FCL) shipments on one side and Less than Container Load (LCL) or Air Freight shipments on the other side are integrated. A Vendor-Managed Inventory (VMI) approach is used: a decision-maker has to find a periodic shipping policy that minimizes the sum of transportation cost and inventory cost, both at the producer and at the customer. This problem is defined at the tactical level implying that the initial inventory levels at the producer and at the customer are not data, but decision variables. For this problem we formulate a Mixed Integer Linear Programming model and prove its computational complexity. Furthermore, we introduce the concept of Value of Integration of FCL and LCL/Air Freight shipments and prove performance bounds to show that the integration of FCL and LCL/Air Freight shipments can lead to significant cost savings, both in the worst case and on average. Systematic computational experiments are finally carried out.

In this paper, we consider a product manufacturer that seeks to leverage the potential of human learning to develop the capacity of its workforce and to reduce its costs. Unlike much of the literature in this area, we do not assume that the rate at which individuals learn is known with certainty. We present a two-stage stochastic programming model of the related production planning problem that quantifies the impact of worker assignment decisions to produce through an exponential learning curve which we linearize to yield a mixed integer linear program that can be solved efficiently. With this stochastic program, we perform a rigorously designed computational study and statistical analysis to derive tactics and managerial insights for how an organization should plan its production operations about assignment, cross-training and practicing. Results suggest that explicitly recognizing uncertainty in learning rates would reduce costs and that when dealing with assignment decisions, the leading factor to consider is the mean learning rate. On the other hand, when dealing with cross-training and practicing decisions, the learning rate variance is more predictive. We also assess the impact of explicitly considering stochastic forgetting rates in the productivity curve, finding that in the optimal assignment schedule, workers practice more and always specialize.

This paper is a report on a joint project by the Department of Management, Economics and Quantitative Methods of the University of Bergamo (in collaboration with the Department of Economics and Management of the University of Brescia) and the Italian company “La Centrale del Latte di Vicenza SpA” producing different types of milk, yogurt, vegetable drinks, cream, butter, cheese, eggs and vegetables. The aim of the project was to provide forecasting methods and optimization models, to improve the demand forecasts of perishable products and to better manage inventory levels in a Material Requirements Planning (MRP) setting.

In this paper we review recent results on the groundstate energy spectra of magnetic knots and links and compare these results with new results on bending energy of tight knots and links obtained by using RIDGERUNNER data on curvature. Remarkable similarities between the two systems are found. Comparative analysis between magnetic and bending energy at groundstate energy level shows that information based on bending energy provides a very good proxy for magnetic end-states.

We present a two-stage stochastic program for a distribution logistic system with transshipment and backordering under stochastic demand and we first argue that it is NP-hard. Then, we perform a computational analysis based on a distribution network. In the case with two retailers, we show that modeling uncertainty with a stochastic program leads to better solutions with respect to the ones provided by the deterministic program, especially if limited recourse actions are admitted. Although there are special cases in which the deterministic and the stochastic solutions select the same retailers towards which sending items, in general, the deterministic solution cannot be upgraded in order to find the optimal solution of the stochastic program. Finally, in the case with four retailers, transshipment can provide more flexibility and better results.

Multistage mixed-integer stochastic programs are among the most challenging optimization problems combining stochastic programs and discrete optimization problems. Approximation techniques which provide lower and upper bounds to the optimal value are very useful in practice. In this paper we present a critic summary of the results in Maggioni et al., J Optim Theory Appl 163:200–229 (2014), [4] and in Maggioni et al., Comput Manag Sci 13:423–457 (2016), [5] where we consider bounds based on the assumption that a sufficiently large discretized scenario tree describing the problem uncertainty is given but is unsolvable. Bounds based on group subproblems, quality of the deterministic solution and rolling-horizon approximation will be then discussed and compared.

In this paper, we consider a recently introduced problem specifically designed for Smart Cities and City Logistics applications: the multi-path travelling salesman problem with stochastic travel costs (mpTSPs)(mpTSPs). The mpTSPsmpTSPs is a variant of the TSP problem where a set of paths exists between any two nodes and each path is characterized by a random travel time. We propose a two-stage stochastic programming formulation where tour design makes up the first stage, while recourse decisions related to the choice of the path to follow are made in the second stage. To solve this formulation, we propose a heuristic method inspired by the Progressive Hedging (PH) algorithm of Rockafellar & Wets (1991, Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res., 16, 119–147.) We then benchmark the solution method by solving model instances derived from the traffic speed sensor network of the city of Turin. Furthermore, the impact of the stochastic travel time costs on the problem solution is examined, showing the benefits of the proposed methodology in both solution quality and computational effort when compared to solving the deterministic equivalent formulation using a commercial solver.

In this paper we analyze the effect of two modelling approaches for supply planning problems under uncertainty: two-stage stochastic programming (SP) and robust optimization (RO). The comparison between the two approaches is performed through a scenario-based framework methodology, which can be applied to any optimization problem affected by uncertainty. For SP we compute the minimum expected cost based on the specific probability distribution of the uncertain parameters related to a set of scenarios. For RO we consider static approaches where random parameters belong to box or ellipsoidal uncertainty sets in compliance with the data used to generate SP scenarios. Dynamic approaches for RO, via the concept of adjustable robust counterpart, are also considered. The efficiency of the methodology has been illustrated for a supply planning problem to optimize vehicle-renting and procurement transportation activities involving uncertainty on demands and on buying costs for extra-vehicles. Numerical experiments through the scenario-based framework allow a fair comparison in real case instances. Advantages and disadvantages of RO and SP are discussed., 34 pages, 5 figures. Under evaluation in an international journal

Homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space have been proposed by Jin et al. in [17]. Alzalg [8] has adopted their work to derive homogeneous selfdual algorithms for stochastic second-order programs with finite event space. In this paper, we generalize these to derive homogeneous selfdual algorithms for stochastic programs with finite event space over the much wider class of all symmetric cones. They include among others, stochastic semidefinite programs and stochastic second-order cone programs.

A facility has to be located in a given area to serve a given number of customers. The position of the customers is not known. The service to the customers is carried out by several traveling salesmen. Each of them has a capacity in terms of the maximum number of customers that can be served in any tour. The aim was to determine the service zone (in a shape of a circle) that minimizes the expected cost of the traveled routes. The center of the circle is the location of the facility. Once the position of the customers is revealed, the customers located outside the service zone are served with a recourse action at a greater unit cost. For this problem, we compare the performance of two different solution approaches. The first is based on a heuristic proposed for the Capacitated Traveling Salesman Problem and the second on the optimal solution of a stochastic second-order cone formulation with an approximate objective function.