2015 ICS Student Paper Award Winner
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 Fortification,” 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 Winner
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.
Runner-up:
- Kalyani Nagaraj, Virginia Tech for 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 Winner
The 2013 Student Paper Award Winner is Jing Xie, Cornell University for 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.
Runner-up:
- Rodrigo Carrasco, Columbia University, "Resource Cost Aware Scheduling." Advisors: Garud Iyengar and Cliff Stein
Award Committee:
- 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.
Runner-up:
- Martin Takáč, University of Edinburgh, for the paper "Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function". Advisor: Peter Richtarik
Award Committee:
- 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.
Award Committee:
- Shabbir Ahmed (chair),
- Peter Frazier and
- Dominique Orban