We consider a class of min-max robust problems in which the functions that need to be “robustified” can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems, such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set, we derive a tractable approximation, called the dual Lagrangian approach, that we relate with both the classical dualization approximation approach and an exact approach. Moreover, we show that the dual Lagrangian approach coincides with the affine decision rule approximation approach. The dual Lagrangian approach is applied to a lot-sizing problem, in which demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period. Using the insights provided by the interpretation of the Lagrangian multipliers as penalties in the proposed approach, two heuristic strategies, a new guided iterated local search heuristic, and a subgradient optimization method are designed to solve more complex lot-sizing problems in which additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics that provide a good compromise between the quality of the robust solutions and the running time required in their computation. Summary of Contribution: The paper includes both theoretical and algorithmic contributions for a class of min-max robust optimization problems where the objective function includes the maximum of a sum of affine functions. From the theoretical point of view, a tractable Lagrangian dual model resulting from a relaxation of the well-known adversarial problem is proposed, providing a new perspective of well-known models, such as the affinely adjustable robust counterpart (AARC) and the dualization technique introduced by Bertsimas and Sim. These results are particularized to lot-sizing problems. From the algorithm point of view, efficient heuristic schemes—which exploit the information based on the interpretation of the Lagrangian multipliers to solve large size robust problems—are proposed, and their performance is evaluated through extensive computational results based on the lot-sizing problem. In particular, a guided iterated local search and a subgradient optimization method are proposed and compared against the dualization approach proposed by Bertsimas and Sim and with several heuristics based on the AARC approach, which include an iterated local search heuristic and a Benders decomposition approach. Computational results show the efficiency of the proposed heuristics, which provide a good compromise between the quality of the robust solutions and the running time.

INOC 2019: 9th International Network Optimization Conference (INOC), Avignon, France, 12-14 June 2019

We consider a stochastic single item production‐inventory‐routing problem with a single producer, multiple clients, and multiple vehicles. At the clients, demand is allowed to be backlogged incurring a penalty cost. Demands are considered uncertain. A recourse model is presented, and valid inequalities are introduced to enhance the model. A new general approach that explores the sample average approximation (SAA) method is introduced. In the sample average approximation method, several sample sets are generated and solved independently in order to obtain a set of candidate solutions. Then, the candidate solutions are tested on a larger sample, and the best solution is selected among the candidates. In contrast to this approach, called static, we propose an adjustable approach that explores the candidate solutions in order to identify common structures. Using that information, part of the first‐stage decision variables is fixed, and the resulting restricted problem is solved for a larger size sample. Several heuristic algorithms based on the mathematical model are considered within each approach. Computational tests based on randomly generated instances are conducted to test several variants of the two approaches. The results show that the new adjustable SAA heuristic performs better than the static one for most of the instances.

Abstract In a previous article, using underlying graph theoretical properties, Gouveia and Magnanti (2003) described several network flow‐based formulations for diameter‐constrained tree problems. Their computational results showed that, even with several enhancements, models for situations when the tree diameter D is odd proved to be more difficult to solve than those when D is even. In this article we provide an alternative modeling approach for the situation when D is odd. The approach views the diameter‐constrained minimum spanning tree as being composed of a variant of a directed spanning tree (from an artificial root node) together with two constrained paths, a shortest and a longest path, from the root node to any node in the tree. We also show how to view the feasible set of the linear programming relaxation of the new formulation as the intersection of two integer polyhedra, a so‐called triangle‐tree polyhedron and a constrained path polyhedron. This characterization improves upon a model of Gouveia and Magnanti (2003) whose linear programming relaxation feasible set is the intersection of three rather than two integer polyhedra. The linear programming gaps for the tightened model are very small, typically less than 0.5%, and are usually one third to one tenth of the gaps of the best previous model described in Gouveia and Magnanti (2003). Moreover, using the new model, we have been able to solve large Euclidean problem instances that are not solvable by the previous approaches. © 2004 Wiley Periodicals, Inc.