We address a variant of the vehicle routing problem with time windows (VRPTW) that includes the decision of how many deliverymen should be assigned to each vehicle. In this variant, the service time at each customer depends on the size of the respective demand and on the number of deliverymen assigned to visit this customer. … Read more
In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three … Read more
Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed- integer programs, problem instances can exceed available memory on a single workstation. To overcome this limitation, we present PIPS-SBB: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels … Read more
Given a p-dimensional nonnegative, integral vector α, this paper characterizes the convex hull of the set S of nonnegative, integral vectors x that is lexicographically less than or equal to α. To obtain a finite number of elements in S, the vectors x are restricted to be component-wise upper-bounded by an integral vector u. We … Read more
In this paper, we study a two-level lot-sizing problem with supplier selection (LSS). This NP-hard problem arises in different production planning and supply chain management applications. We first present a dynamic programming algorithm for LSS that is polynomial when the number of plants is fixed. We use this algorithm to describe the convex hull of … Read more
We consider the decision problem of making causal conclusions from observational data. Typically, using standard matched pairs techniques, there is a source of uncertainty that is not usually quanti fied, namely the uncertainty due to the choice of the experimenter: two di fferent reasonable experimenters can easily have opposite results. In this work we present an alternative … Read more
Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more
The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more
We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, … Read more
We consider a class of fixed-charge transportation problems over graphs. We show that this problem is strongly NP-hard, but solvable in pseudo-polynomial time over trees using dynamic programming. We also show that the LP formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Given these results, we present … Read more