Publications
- G. Angulo, M. Van Vyve. Fixed-charge transportation problems on trees.
Submitted, 2015. Preprint. [Abstract]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 a unary expansion-based formulation for general graphs that is computationally advantageous when compared to a standard formulation, even if its LP relaxation is not stronger.
- G. Angulo, S. Ahmed, S. S. Dey. Improving the integer L-shaped method.
Submitted, 2015. Preprint. [Abstract]We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Then, to better approximate the shape of the second-stage cost function, we present a general framework to generate optimality cuts via a cut-generating linear program which considers information from all solutions found up to any given stage of the method. In order to address the impact of the proposed approaches, we report computational results on two classes of stochastic integer problems.
- G. Angulo, S. Ahmed, S. S. Dey, V. Kaibel. Forbidden vertices.
Mathematics of Operations Research 40(2):350-360, 2015. Journal. Preprint. [Abstract]In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations when P has binary vertices only. Some applications and extensions to integral polytopes are discussed.
- G. Angulo, S. Ahmed, S. S. Dey. Semi-continuous Network Flow Problems.
George Nicholson Student Paper Competition, honorable mention, 2013.
Mathematical Programming 145(1-2):565-599, 2014. Journal. Preprint. [Abstract]We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems.
- R. Epstein, A. Neely, A. Weintraub, F. Valenzuela, S. Hurtado, G. Gonzalez, A. Beiza, M. Naveas, F. Infante, F. Alarcon, G. Angulo, C. Berner, J. Catalan, C. Gonzalez, D. Yung. A Strategic Empty Container Logistics Optimization in a Major Shipping Company.
Franz Edelman Award, finalist, 2011. Details.
Interfaces 42(1):5-16, 2012. Journal. [Abstract]In this paper, we present a system that Compañía Sud Americana de Vapores (CSAV), one of the world's largest shipping companies, developed to support its decisions for repositioning and stocking empty containers. CSAV's main business is shipping cargo in containers to clients worldwide. It uses a fleet of about 700,000 TEU containers of different types, which are carried by both CSAV-owned and third-party ships. Managing the container fleet is complex; CSAV must make thousands of decisions each day. In particular, imbalances exist among the regions. For example, China often has a deficit of empty containers and is a net importer; Saudi Arabia often has a surplus and is a net exporter. CSAV and researchers from the University of Chile developed the Empty Container Logistics Optimization System (ECO) to manage this imbalance. ECO's multicommodity, multiperiod model manages the repositioning problem, whereas an inventory model determines the safety stock required at each location. CSAV uses safety stock to ensure high service levels despite uncertainties, particularly in the demand for containers. A hybrid forecasting system supports both the inventory and the multicommodity network flow model. Major improvements in data gathering, real-time communications, and automation of data handling were needed as input to the models. A collaborative Web-based optimization framework allows agents from different zones to interact in decision making. The use of ECO led to direct savings of $81 million for CSAV, a reduction in inventory stock of 50 percent, and an increase in container turnover of 60 percent. Moreover, the system helped CSAV to become more efficient and to overcome the 2008 economic crisis.
Technical reports
- G. Angulo, S. Ahmed, S. S. Dey. Forbidding extreme points from the 0-1 hypercube. Preprint.
[Abstract]
Let B be the set of n-dimensional binary vectors and let V be a subset of m of its elements. We give an extended formulation of the convex hull of B\V which is polynomial in n and m. In developing this result, we give a two-sided extension of a result in Laurent and Sassano (1992) for knapsack sets with superincreasing coefficients.
Presentations
- G. Angulo. On semicontinuous relaxations of fixed-charged network flow problems.
INFORMS Annual Meeting, Philadelphia, PA, 2015.
ISE Seminar, Virginia Tech, Blacksburg, VA, 2014. - G. Angulo, S. Ahmed, S. Dey, V. Kaibel. Forbidden vertices.
CORE Operations Research Seminar, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2014.
CAAM Colloquium, Rice University, Houston, TX, 2013.
ACO Student Seminar, Georgia Institute of Technology, Atlanta, GA, 2013.
INFORMS Annual Meeting, Minneapolis, MN, 2013. - G. Angulo, S. Ahmed, S. Dey. Improving the integer L-shaped method.
INFORMS Optimization Society Conference (IOS), Houston, TX, 2014. - G. Angulo, S. Ahmed, S. Dey, V. Kaibel. Forbidding solutions in (integer) linear programming.
DOS Optimization Seminar, Georgia Institute of Technology, Atlanta, GA, 2013. - G. Angulo, S. Ahmed, S. Dey. Improved optimality cuts for the integer L-shaped method.
INFORMS Annual Meeting, Minneapolis, MN, 2013.
XIII International Conference on Stochastic Programming (ICSP), Bergamo, Italy, 2013.
INFORMS Annual Meeting, Phoenix, AZ, 2012. - G. Angulo, S. Ahmed, S. Dey. Semi-continuous Network Flow Problems.
INFORMS Annual Meeting, Minneapolis, MN, 2013.
International Symposium on Mathematical Programming (ISMP), Berlin, Germany, 2012.
INFORMS Annual Meeting, Phoenix, AZ, 2012. - G. Angulo, S. Ahmed, S. Dey. Cutting Planes for Semi-continuous Network Flow Problems.
DOS Optimization Seminar, Georgia Institute of Technology, Atlanta, GA, 2011.
INFORMS Annual Meeting, Charlotte, NC, 2011. - G. Angulo, D. Moran, R. Lopez, D. Espinoza. Kimberly-Clark logistics optimization.
XIV Latin-American Summer School on Operations Research (ELAVIO), El Fuerte, Mexico, 2009. - G. Angulo, A. Weintraub. Empty container movement optimization under uncertainty.
XIV Latin-American Conference on Operations Research (CLAIO), Cartagena de Indias, Colombia, 2008. - G. Angulo, A. Weintraub. Robust Optimization applied to jail location in Chile.
XII Latin-American Summer School on Operations Research (ELAVIO), Petropolis, RJ, Brazil, 2007.
Posters
- G. Angulo, S. Ahmed, S. Dey, V. Kaibel. Forbidden vertices.
Best Poster Competition, honorable mention. Details.
MIP 2013, Madison, WI, 2013. - G. Angulo, S. Ahmed, S. Dey. Improved optimality cuts for the integer L-shaped method.
MIP 2012, Davis, CA, 2012. - G. Angulo, S. Ahmed, S. Dey. Cutting Planes for Semi-continuous Network Flow Problems.
MIP 2011, Waterloo, ON, 2011. - G. Angulo, R. Carvajal, G. Nemhauser. Information Based Tree Search.
INFORMS Annual Meeting, Austin, TX, 2010.