2018 ICS Student Paper Award
The 2018 INFORMS Computing Society Student Paper Award winner is Aleksandr M. Kazachkov of the Carnegie Mellon University for the paper, "V-Polyhedral Disjunctive Cuts." Aleksandr's advisor and co-author is Dr. Egon Balas.
The citation for this award:
This paper develops a novel approach - based on so-called V-Polyhedral Cuts (VPCs) - for generating valid inequalities when solving mixed-integer linear programming (MILP) problems. The cuts are motivated by several shortcomings of existing cut generation techniques, such as issues related to numerical instability and a "tailing off" effect when they are used recursively. The use of VPCs mitigates such effects by providing a practical method for generating strong cuts without recursion. Theoretical properties of such cuts are presented and computational tests of their performance are conducted. The computational results indicate that the cuts generated are strong and that there appear to exist classes of MILP instances for which VPCs work especially well.
Runners-up for this award, in alphabetical order, were:
- Colin P. Gillen, University of Pittsburgh, "Fortification Against Cascade Propagation Under Uncertainty".
- Chris Lourenco, Texas A&M University, "Asymptotically Optimal Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization".
2018 ICS Student Paper Award Selection Committee
- Sergiy Butenko (Texas A&M University, Industrial and Systems Engineering)
- Frank E. Curtis (Lehigh University, Industrial and Systems Engineering)
- Anna Nagurney - Chair (University of Massachusetts Amherst, Isenberg School of Management)
2017 ICS Student Paper Award
The 2017 INFORMS Computing Society Student Paper Award winner is Berk Ustun of the Massachusetts Institute of Technology for the paper, "Learning Optimized Risk Scores from Large-Scale Datasets." Berk's advisor and co-author is Dr. Cynthia Rudin.
The citation for this award:
This paper considers the question of how to learn risk scores from large datasets in a principled manner. Risk scores are ubiquitous tools used to make crucial predictions such as the risk of seizure for ICU patients. However, despite their widespread use, most risk scores have been developed in an ad hoc manner. This has been the case since learning risk scores from data is particularly challenging, especially in the presence of inconvenient operational constraints that translate as the need for sparsity, small-integer coefficients, and rank- accuracy. In this paper, the authors pose the risk score identification problem as a mixed-integer nonlinear program, and present a novel cutting-plane algorithm that recovers the optimal solution efficiently. The cutting plane algorithm is shown to scale linearly with the size of the dataset, and requires little to no parameter tuning. The generality of the formulation and the strength of the numerical experiments are illustrative of the high potential impact of this work.
Runners-up for this award, in alphabetical order, were:
- Rui Gao, Georgia Institute of Technology, "Wasserstein Distributional Robustness and Regularization in Statistical Learning"
- Christian Kroer, Carnegie Mellon University, "Theoretical and Practical Advances on Smoothing for Extensive-Form Games"
- Hamed Rahimian, The Ohio State University, "Identifying Effective Scenarios in Distributionally Robust Stochastic Programs with Variation Distance"
2017 ICS Student Paper Award Selection Committee
- Raghu Pasupathy, Chair
- Frank Curtis
- Anna Nagurney
2016 ICS Student Paper Award
The 2016 INFORMS Computing Society Student Paper Award winner is Georgina Hall of Princeton University for the paper, "DC Decomposition of Nonconvex Polynomials with Algebraic Techniques." She is advised by Prof. Amir Ali Ahmadi.
Runners-up, in alphabetical order, were:
- Hadi Charkhgard, University of Newcastle, "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method"
- Terrence Mak, Australian National University, "Dynamic Compressor Optimization in Natural Gas Pipeline Systems"
2016 ICS Student Paper Award Selection Committee
- Hande Benson, Chair
- Anna Nagurney
- Raghu Pasupathy
2015 ICS Student Paper Award
The 2015 INFORMS Computing Society Student Paper Award winner is Young Woong Park (formerly of Northwestern University), for the paper, "An Aggregate and Iterative Disaggregate Algorithm with Proven Optimality in Machine Learning."
Advisor: Diego Klabjan
The paper considers machine learning problems, with particular focus on least absolute deviation regression, support vector machine, and semi-supervised support vector machine problems, arising in the presence of a large amount of data, and under the premise that the size of the existing data renders the use of "out-of-the-box" solution algorithms inefficient. The authors propose a novel aggregation-disaggregation idea, where a solution is attained iteratively, by solving the given problem on a sequence of gradually disaggregated datasets. Efficiency stems from the reduced complexity of solving the problem on smaller datasets and the use of solutions from previous problems (on more aggregated datasets) as warm-starts for subsequent problems. The authors propose model-specific aggregation and disaggregation procedures, demonstrate convergence, and derive optimality gaps for these specific but widely used machine learning problems. Perhaps more importantly, the proposed ideas suggest a paradigm that could prove useful for solving a wider range of problems arising in similar "big data" contexts. The reported numerical experience is compellingly in favor of the proposed algorithm.
Runners-up (in alphabetical order):
- Xiao Liu, "Decomposition Algorithms for Two-Stage Chance-Constrained Programs," Advisors: Simge Kucukyavuz and James Luedtke.
- Leonardo Lozano, "A Backward Sampling Framework for Interdiction Problems with Forti cation,” Advisor: J. Cole Smith
- Jorge A. Sefair, "Dynamic Shortest-Path Interdiction,” Advisor: J. Cole Smith
2015 ICS Student Paper Award Selection Committee
- David Morton, Chair
- Hande Benson
- Raghu Pasupathy
2014 ICS Student Paper Award
The 2014 INFORMS Computing Society Student Paper Award Winner is Andre A. Cire, Carnegie Mellon University for the paper, "Multi-Valued Decision Diagrams for Sequencing Problems."
Co-Advisors: Willem-Jan van Hoeve and John Hooker
The paper considers sequencing problems that are at the heart of scheduling and routing applications. In particular, it introduces Multi-Valued Decision Diagrams (MDDs) as a fundamental representation for the state constraints accounting for precedence, time windows and setup times within a sequencing problem. The paper articulates how to leverage the MDD to offer different filtering strengths through width-relaxation and provide bounds on the objective function. It also articulates how the MDD can infer precedence constraints between activities. The paper also discusses how a strengthening technique exploiting job priorities can derive sharper representations for high-priority jobs, yielding a more accurate representation of the permutations referring to those jobs. The benefit is demonstrated with the derivation of a polynomial time algorithm for a variant of the TSP introduced by Balas in 1999. The paper offers compelling computational results in which using the MDD alone or in conjunction with the classic edge-finder propagator yields order-of-magnitude improvements in runtime and in search efforts. In addition, the paper closes three open instances from the TSPLIB for the sequential ordering problem.
- Kalyani Nagaraj, Virginia Techfor the paper, "Stochastically Constrained Simulation Optimization on Integer-Ordered Spaces: The cgR-SPLINE Algorithm."
- Advisor: Raghu Pasupathy
The 2014 ICS Student Paper Award Committee members are:
- Hande Benson (Drexel University),
- Laurent Michel, Chair (University of Connecticut), and
- Dave Morton (UT Austin).
2013 ICS Student Paper Award
The 2013 Student Paper Award Winner is Jing Xie, Cornell Universityfor the paper, "Sequential Bayes-Optimal Policies for Multiple Comparisons with a Known Standard."
Advisor: Peter Frazier
This paper considers the statistical ranking & selection problem of multiple comparisons with a standard in the stochastic simulation setting. Specifically, given a set of alternatives with unknown mean performances, the goal is to find the optimal sequential allocation of simulation replications for determining which of the alternatives' mean performances exceeds a given performance threshold. Under a Bayesian dynamic programming formulation and using techniques from optimal stopping and multi-armed bandit problems, this paper is able to explicitly and efficiently compute the sequential Bayes-optimal for a very general class of sampling distributions: the well-known exponential family, which includes the most common continuous and discrete distributions such as normal, gamma, Poisson, geometric, and binomial. Computational experiments comparing the policy with other sampling policies in the literature demonstrate the effectiveness of the implemented sequential algorithm. Overall, the paper is well written and makes important contributions to both the theory and practice of simulation optimization by using a rigorous modeling framework that leads to useful implementable algorithms.
- Rodrigo Carrasco, Columbia University, "Resource Cost Aware Scheduling."
- Advisors: Garud Iyengar and Cliff Stein
- Laurent Michel (University of Connecticut),
- Cindy Phillips (Sandia), and
- Michael Fu, Chair (University of Maryland).
2012 ICS Student Paper Award Winner
The 2012 Student Paper Award Winner is Huashuai Qu (University of Maryland) for the paper, "Simulation Selection with Unknown Correlation Structures."
Advisors: Michael Fu and Ilya Ryzhov
This paper considers the problem of Bayesian optimization via simulation, with correlated prior beliefs and correlated sampling with an unknown sampling covariance matrix. This problem arises when performing optimization via simulation with common random numbers, and is important because sampling with common random numbers has the potential to allow better efficiency than does independent sampling. Analysis of this problem, however, is substantially more difficult than with independent sampling as there is no conjugate prior distribution permitting sequential sampling, making computation of the posterior distribution computationally challenging. This paper deftly steps around this difficulty by using an approximation based on minimizing the Kullback-Leibler divergence, which provides a computationally tractable approximate posterior distribution. Then, using this statistical technique as a foundation, this paper develops a new value of information sampling procedure that allows unknown correlation structures. This procedure has better performance than existing procedures on several problems, and it shows that modeling the unknown sampling covariance matrix can have a significant effect on the value of information. This work has broader implications for other problems in simulation optimization, and more broadly in sequential experimental design: it provides an appealing methodology for approximating posterior distributions in other sequential sampling problems; and it paves the way for unknown covariance matrices to be modeled explicitly, rather than assumed known, in other problems requiring sequential value-of-information analysis.
- Martin Takáč, University of Edinburgh, for the paper "Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function".
- Advisor: Peter Richtarik
- Peter Frazier,
- Cynthia A. Phillips,
- Andreas S. Schulz (chair)
2011 ICS Student Paper Award Winner
The 2011 ICS Student Paper Award Winner is Susan Hunter (Virginia Tech) for the paper, "Optimal Sampling Laws for Stochastically Constrained Simulation Optimization on Finite Sets."
Advisor: Raghu Pasupathy
The paper considers an important but little-studied problem from simulation optimization: select the best of finitely many noisy systems, subject to one or more stochastic constraints. Under general distributional assumptions, this paper provides the first exact characterization of the allocation of simulation samples to systems that maximizes the asymptotic rate at which the probability of correctly selecting the best converges to one. This characterization is as the solution to a concave maximization problem. The paper then provides an implementable algorithm whose allocation converges to this optimal allocation.
This clearly written and innovative paper makes an important contribution to simulation optimization by bringing together techniques borrowed from several branches of the fields of operations research and computing.
- Shabbir Ahmed (chair),
- Peter Frazier and
- Dominique Orban
2010 ICS Student Paper Award Winner
The 2010 Student Paper Award Winner is Yongqiang Wang (University of Maryland, College Park) for the paper, "A New Stochastic Derivative Estimator for Discontinuous Payoff Functions with Application to Financial Derivatives."
Advisors: Michael C. Fu and Steven I. Marcus
- Siqian Shen, University of Florida, for the paper "Expectation and Chance-constrained Models and Algorithms for Insuring Critical Paths"
Advisors Cole Smith and Shabbir Ahmed.
- Necdet Aybat, for the paper "A First-order Augmented Lagrangian Method for Compressed Sensing"
Advisor Garud Iyengar.
Award Committee: Ted Ralphs (chair), Ed Baker, John Mitchell
Sponsored by the Mica Fonden.
2009 ICS Student Paper Award Winner
The 2009 ICS Student Paper Award Winner is Zaiwen Wen (Columbia University) for the paper, "A Line Search Multigrid Method for Large-Scale Nonlinear Optimization."
Advisor: Donald Goldfarb
- Mehmet Begen, University of British Columbia, for the paper "Appointment Scheduling with Discrete Random Durations"
Advisor Maurice Queyranne.
- Peter Frazier, Princeton University, for the paper "Knowledge-Gradient Methods for Statistical Learning"
Advisor Warren Powell.
Award Committee: Alexander Shapiro (chair), Bill Cook, ...
2008 ICS Student Paper Award Winner
The 2008 ICS Student Paper Award Winner is Guanghui Lan (Georgia Institute of Technology) for the paper, "Efficient Methods for Stochastic Composite Optimization."
Advisors: Arkadi Nemirovski, Renato Monteiro and Alexander Shapiro
Award Committee: David Morton (chair), Alper Atamturk, Nick Sahinidis
2007 ICS Student Paper Award Winner
The 2007 ICS Student Paper Award Winner is Amit Partani for the paper, "Adaptive Jackknife Estimators for Stochastic Programming."
Advisor: David Morton
Award Committee: Jonathan Eckstein (chair), Michael Trick, Jeff Linderoth
- Andrea Bettinelli for "A Branch-and-Price Algorithm for the Two-Dimensional Level Strip Packing Algorithm"
- Richa Agarwal for "Ship Scheduling and Network Design for Cargo Routing in Liner Shipping"
2006 ICS Student Paper Award Winner
2006 ICS Student Paper Award Winner Geng Deng for the paper, "Variable-Number Sample-Path Optimization."
Advisor: Michael C. Ferris.
- Jiaqiao Hu, University of Maryland, College Park, for the paper "A Model Reference Adaptive Search Method for Global Optimization"
Adviors Steven Marcus and Michael Fu.
- Laura A. McLay, University of Illinois, for the paper "An Analysis of Knapsack Problems with Set-Up Weights"
Advisor Sheldon H. Jacobson.
2006 ICS Student Paper Award Committee:
- David Woodruff (Chair)
- David Gay
- David Shanno