This paper deals with the ring star problem that consists in designing a ring that pass through a central depot, and then assigning each non visited customer to a node of the ring. The objective is to minimize the total routing and assignment costs. A new chain based formulation is proposed. Valid inequalities are proposed … Read more
We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more
The value function of a mixed-integer linear program (MILP) is a function that returns the optimal solution value as a function of the right-hand side. In this paper, we analyze the structure of the value function of a MILP with a single constraint. We show that the value function is uniquely determined by a finite … Read more
Given a non empty polyhedral set, we consider the problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This nonsmooth combinatorial optimization problem is NP-Hard and arises in various fields such as machine learning, pattern recognition, signal processing. We propose two … Read more
The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit … Read more
Dynamic stochastic optimization problems with a large (possibly infinite) number of decision stages and high-dimensional state vector are inherently difficult to solve. In fact, scenario tree based algorithms are unsuitable for problems with many stages, while dynamic programming type techniques are unsuitable for problems with many state variables. This article proposes a stage aggregation scheme … Read more
This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of … Read more
We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region constraint. The Steihaug-Toint method uses the conjugate-gradient (CG) algorithm to minimize the quadratic over a sequence of expanding subspaces until the iterates either converge to an interior point or cross the constraint boundary. … Read more
We present a data-driven forecasting technique with integrated inventory control for seasonal data and compare it to the traditional Holt-Winters algorithm. Results indicate that the data-driven approach achieves a 2-5% improvement in the average regret. Citation Technical Report, Lehigh University, Department of Industrial and Systems Engineering, Bethlehem, PA. Article Download View Integrated Forecasting and Inventory … Read more
A numerical study of model-based methods for derivative-free optimization is presented. These methods typically include a geometry phase whose goal is to ensure the adequacy of the interpolation set. The paper studies the performance of an algorithm that dispenses with the geometry phase altogether (and therefore does not attempt to control the position of the … Read more