ISE Seminar Series
Purpose
The purpose of the seminars are to expose the ISE graduate and Ph.D. students to new fields of research and topics of study. Featured faculty and researchers from other universities visit the department throughout the year and explain their research to faculty and students.
*Please note: it is mandatory for ISE Department Ph.D. students to attend all seminars.*
Jacqueline Griffin ’05, ’06G
Title: The Bed Managers Dilemma: A Dynamic Bed Assignment Problem
Assistant Professor
Mechanical and Industrial Engineering, Northeastern University
Wednesday, December 5, 2012
4:00pm
Mohler Lab Room 451
ABSTRACT
The role of hospital bed management staff and processes has gained increased attention in recent years due to the impact of bed management practices on hospital performance metrics including average boarding time, patient safety, overflow rate, and patient diversions. One of the key tasks of the bed manager is to balance the available capacity with competing requests for beds, accounting for the unique requirements and clinical characteristics of the patients, and expectations about future demand and patient discharges. Due to the constantly changing system state, the process of matching patients with beds is similar to a dynamic assignment problem. We identify structural properties of the bed assignment process, by modeling the hospital system as a tandem queueing network with multiple customer classes and cross-trained server pools. Utilizing these properties we develop new algorithms for making dynamic assignment decisions and test the performance against current hospital bed assignment practices with simulation.
BIOGRAPHY
Jackie Griffin is an Assistant Professor in the Mechanical and Industrial Engineering Department at Northeastern University. Her primary research interests include applications of Operations Research in health and humanitarian systems. In particular, her focus is on multi-objective resource allocation models. Jackie has partnered with a variety of organizations including the Centers for Disease Control and Prevention (CDC), Childrens Healthcare of Atlanta, DeKalb Medical Womens Center, Emory University Hospital, Grady Memorial Hospital, and World Vision. She was awarded the Global Impact Scholarship and Chaddick Award by the ARCS (Achievement Rewards for College Scientists) Foundation in 2010 and 2011, respectively. She received her PhD from the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Additionally, she completed her MS and BS degrees in the Industrial and Systems Engineering department at Lehigh University.
Jim Luedtke
Title: Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
Assistant Professor
Industrial and Systems Engineering, University of Wisconsin-Madison
Wednesday, November 28, 2012
4:00pm
Mohler Lab Room 451
Jim Luedtke's Power point slides.
ABSTRACT
We study the design of reliably connected networks. Given a graph with arcs that may fail at random, the goal is to select a minimum cost set of arcs such that a connectivity requirement is met with high probability. We first compare this model with a well-known deterministic model of reliable network design: survivable network design. We demonstrate that, if distributional information on arc failures is known, the chance constraint model can yield a significantly richer set of solutions on the efficient frontier of reliability and cost. We then present two solution approaches for our model, which we formulate as a chance-constrained stochastic integer program. The first approach is based on a formulation that uses binary variables to determine if the connectivity requirement is satisfied in each arc failure scenario, and enforces the connectivity requirement in selected scenarios using scenario-based graph cuts. We derive additional classes of valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on the idea of probabilistic graph cuts, which is an extension of graph cuts to graphs with random arc failures. Inequalities defined by such cuts are sufficient to define the set of feasible solutions and can be separated efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results will be presented.
This is joint work with Yongjia Song.
BIOGRAPHY
Jim Luedtke is an Assistant Professor in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Luedtke earned his Ph.D. at Georgia Tech and did a postdoc at the IBM T.J. Watson Research Center. Luedtke's research lies in the areas of stochastic and mixed-integer programming, with interest in applications in service systems and energy. In stochastic programming, funded by an NSF CAREER award, Luedtke has focused on models and algorithms for risk-constrained optimization. In mixed-integer programming, Luedtke is currently studying mixed-integer nonlinear sets with the goal of finding strong and efficiently solvable convex relaxations.
Immanuel M. Bomze
Title: A nasty cone with nice properties - new issues in Copositive Optimization
University of Vienna
Monday, November 19, 2012
2:00pm
Mohler Lab Room 451
ABSTRACT
A symmetric matrix is called copositive, if it generates a quadratic form taking no negative values over the positive orthant. Contrasting to positive-semide niteness, checking copositivity is NP-hard. In a copositive optimization problem, we have to minimize a linear function of a symmetric matrix over the copositive cone subject to linear constraints. This convex program has no non-global local solutions. On the other hand, there are several hard non-convex programs which can be formulated as copositive programs, among them mixed-binary QPs or Standard QPs. Applications range from machine learning, optimization under uncertainty, to several combinatorial optimization problems, including the maximum-clique problem or the maximum-cut problem.
The dual conic program, unlike the more popular SDP case, involves a different matrix cone, that of completely positive matrices (those which allow for a symmetric, possibly rectangular factorization with no negative entries). This conic optimization technique shifts complexity from global optimization towards sheer feasibility questions. Therefore it is of central importance to devise positive and negative certifcates of copositivity and/or complete positivity.
BIOGRAPHY
Immanuel M. Bomze was born in Vienna, Austria, in 1958. He received the degree Magister rerum naturalium in Mathematics at the University of Vienna in 1981. After a postgraduate scholarship at the Institute for Advanced Studies, Vienna from 1981 to 1982, he received the degree Doctor rerum naturalium in Mathematics at the University of Vienna. He held several visiting research positions at the International Institute for Applied Systems Analysis, Laxenburg, Austria, at the Institute for Advanced Studies, Vienna, at the Department of Economics, University of Melbourne, Australia, and at the Department of Mathematics, Wilfrid Laurier University,Waterloo, ON, Canada. Since 2004, he holds a chair (full professor) of Applied Mathematics and Statistics at the University of Vienna. His research interests are in the areas of nonlinear optimization, qualitative theory of dynamical systems, game theory, mathematical modeling and statistics, where he has edited one and published four books, as well as over 80 peer-reviewed articles in scienti c journals and monographs. The list of his coauthors comprises almost sixty scientists from a dozen countries in four continents.
As a member of program and/or organizing committees, he co-organized various scientifc events and he is an Associate Editor for ve international journals. For several Science Foundations and Councils (based in Germany, Great Britain, Israel, Italy, the Netherlands, Portugal, Spain, USA), and for almost 50 scientifc journals he acted as a reporting referee. Currently he serves as an Editor of the European Journal of Operational Research, one of the worldwide leading journals in the field.
Gillian Chin, PhD Candidate
Title: Second Order Methods for Large-Scale Machine Learning
Department of Industrial Engineering and Management Sciences, Northwestern University
Friday, November 16, 2012
2:30pm
Mohler Lab Room 451
ABSTRACT
We will explore the development of efficient batch optimization algorithms for solving large-scale statistical learning applications; particularly those that can be formulated as a nonlinear programming problem. We rst investigate smooth, unconstrained problems, with applications in speech recognition. To reduce the computational cost of the optimization process, we will introduce two effective strategies, being: stochastic Hessian information and dynamic gradient sampling. We will then focus on developing second order methods for non-smooth optimization problems, speci cally in devising a semi-smooth Newton framework that can be used to generate several popular methods for machine learning.
BIOGRAPHY
Gillian Chin is a Ph.D. Candidate at Northwestern University in the Department of Industrial Engineering and Management Sciences in Evanston, Illinois. She received her BASc. in Industrial Engineering from the University of Toronto, Canada in 2008, with Honours. Her Ph.D. adviser is Dr. Jorge Nocedal, and the focus of her dissertation is developing efficient optimization algorithms for large{scale machine learning and nonlinear programming, with additional emphasis on sparse problems. She has held internships at Google Research and Argonne National Laboratory, and has been supported by fellowships from the Natural Sciences and Engineering Research Council of Canada (NSERC), and the Northwestern Cabell Fellowship.
Endre Boros
Title: Quadratization of Pseudo-Boolean Functions
Professor and Director
Rutgers Center for Operations Research (RUTCOR)
Wednesday, November 7, 2012
4:00pm
Mohler Lab Room 451
ABSTRACT
Set functions, i.e., real mappings form the family of subsets of a nite set to the reals are known and widely used in discrete mathematics for almost a century, and in particular in the last 50 years. If we replace a finite set with its characteristic vector, then the same set function can be interpreted as a mapping from the set of binary vectors to the reals. Such mappings are called pseudo-Boolean functions and were introduced in the works of Peter L. Hammer in the 1960s. Pseudo-Boolean functions are di erent from set functions, only in the sense that their algebraic representation, a multilinear polynomial expression, is usually assumed to be available as an input representation.
The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc. Some of these applications lead to the minimization of a quadratic pseudo- Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality, and aims at nding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems. The method in fact was found very e ective in computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value. This algorithm was used by computer vision experts and a very ecient implementation, called QPBO, is freely downloadable.
In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of those. This is joint research with Alex Fix, Ramin Zabih (Cornell), and Aritanan Gruber (Rutgers).
BIOGRAPHY
Dr. Endre Boros is a Distinguished Professor of Rutgers University, the State University of New Jersey, and Director of the Operations Research Center (RUTCOR). He is the author of over 15 book chapters and edited volumes, and over 165 research papers published in refereed journals and reviewed conference proceedings. Dr. Boros research interests cover a wide range of topics in discrete mathematics and operations research, including combinatorics, graph theory, combinatorial optimization, integer programming, algorithmic game theory, the theory of Boolean functions, and learning theory. Dr. Boros organized numerous workshops and sessions in larger conferences on Boolean and pseudo-Boolean optimization and is in charge of the corresponding stream of sessions at the EURO meetings. He is on the editorial boards of numerous international journals, Associate Editor of the Annals of Mathematics and Artifcial Intelligence, and Editor-in-Chief of two major journals of his area, the Annals of Operations Research and Discrete Applied Mathematics.
Daniel Steffy
Title: Exact solutions to Linear and Integer Programming problems
Assistant Professor
University of Oakland, Rochester, MI
Wednesday, October 31, 2012
4:00pm
Mohler Lab Room 451
ABSTRACT
The software systems commonly used to solve linear and integer programming problems today make use of oating-point computation and the inexactness of these computations can lead to errors in the returned results. Although such numerical errors are sometimes tolerable, there are situations when exact results are necessary. This talk will describe a variety of methods for computing exact solutions to LPs and MIPs over the rational numbers. A straightforward approach to obtain exact results could be to replace the oating-point operations in current software entirely by exact rational arithmetic; unfortunately, this approach can increase the running times dramatically, motivating the development of more sophisticated techniques. As an alternative, many recently developed methods use a hybrid approach, combining numeric and exact computation.
The key observation is that, although numerically obtained results are not necessarily correct, one can often extract useful information that can be used to reduce the number of exact computations necessary to arrive at an exact solution. We will start by describing an iterative re nement procedure for computing extended precision and exact solutions to LPs. Arbitrarily precise solutions are computed by solving a sequence of closely related LPs with limited precision arithmetic. Exact arithmetic is used only for some inexpensive bookkeeping operations and to reconstruct the exact rational solution, either by rounding an approximate solution to a suitable rational representation or by recomputing the corresponding basic solution exactly. Next we discuss the use of hybrid methods for exact MIPs. In particular, within a branch-and-bound process, we compare di erent strategies for computing valid LP dual bounds. Extensive computational results will be presented showing that exact solutions can often be obtained without a large overhead, compared to inexact methods. (Includes joint work with Bill Cook, Ambros Gleixner, Thorsten Koch and Kati Wolter)
BIOGRAPHY
Dan Steffy is an Assistant Professor in the Department of Mathematics and Statistics at Oakland University in Rochester, MI. He received a Ph.D. in Algorithms, Combinatorics and Optimization from the Georgia Institute of Technology (2011), a M.A. (2005) and B.S. (2004) in Mathematics from Oakland University. Dr. Ste y also spent one year as a post-doctoral researcher at the Zuse Institute Berlin. His research interests include Optimization, Operations Research and Computer Algebra.
Margaret L. Brandeau
Title: Operations Research and Public Health: A Little Help Goes a Long Way
Professor of Management Science and Engineering
Professor of Medicine (by Courtesy)
Stanford University
Friday, October 26, 2012
2:30pm
Mohler Lab Room 451
Presentation slides.
ABSTRACT
How should the Centers for Disease Control and Prevention revise national immunization recommendations so that gaps in vaccination coverage will be filled in a cost-effective manner? What is the most cost-effective way to use limited HIV prevention and treatment resources? To what extent should local communities stockpile antibiotics for response to a potential bioterror attack? This talk will describe examples from past and ongoing model-based analyses of public health policy questions. We also provide perspectives on key elements of a successful policy analysis and discuss ways in which such analysis can influence policy.
BIOGRAPHY
Margaret Brandeau is Coleman F. Fung Professor of Engineering and Professor of Medicine (by Courtesy) at Stanford University. Her research focuses on the development of applied mathematical and economic models to support health policy decisions. Her recent work has focused on HIV prevention and treatment programs, programs to control the spread of hepatitis B virus, and preparedness plans for bioterror response. She is a Fellow of the Institute for Operations Research and Management Science (INFORMS), and has received the President’s Award from INFORMS (recognizing important contributions to the welfare of society), the Pierskalla Prize from INFORMS (for research excellence in health care management science), a Presidential Young Investigator Award from the National Science Foundation, and the Eugene L. Grant Teaching Award from Stanford, among other awards. She is currently a member of the Board of Scientific Counselors, a Federal Advisory Committee to the Office of Public Health Preparedness and Response of the Centers for Disease Control and Prevention, and a member of the Board of Scientific Counselors/National Biodefense Science Board Working Group for the Strategic National Stockpile (SNS) Review 20/20. Professor Brandeau earned a BS in Mathematics and an MS in Operations Research from MIT, and a PhD in Engineering-Economic Systems from Stanford University.
Florian A. Potra
Title: Interior Point Methods for Protein Image Alignment
Professor, Department of Mathematics and Statistics
University of Maryland, Baltimore County
Friday, September 28, 2012
2:30pm - 3:30pm
Mohler Lab Room 451
ABSTRACT
One of the core technologies for obtaining protein mixtures is provided by the two dimensional polyacrylamide gel electrophoresis (2D-gel). In order to analyze variations in the protein gels obtained from different groups that account for biological variations we must first eliminate distortions to properly align images. The image alignment is recognized as a major bottleneck in proteomics. We formulate the image alignment problem as a large scale quadratic programming problem, which can be solved in polynomial time by interior point methods. Unlike previous approaches which are based on pairwise alignment, we use the information contained in the whole family of gels for creating an ideal gel and simultaneously determining the transformations that optimally align all images to this ideal gel. The ideal landmarks and the coefficients defining the transformations are the unknowns of the quadratic programming problem. The constraints of the problem ensure smoothness and consistency. Numerical results illustrate the effectiveness of this approach.
BIOGRAPHY
Florian Potra earned a Ph.D. in Mathematics from the University of Bucharest, Romania. After an Andrew Mellon Postdoctoral Fellowship at the University of Pittsburgh, he joined the faculty of the University of Iowa, first as an Associate Professor of Mathematics, and then as a Professor of Mathematics and Computer Science. Between 1997-1998, he served as a Program Director in Applied and Computational Mathematics at the National Science Foundation. Since 1998 he has been a Professor of Mathematics and Statistics at the University of Maryland Baltimore County. He is also a Faculty Appointee at the Mathematical and Computational Sciences Division of The National Institute of Standards and Technology. Dr. Potra has published over 120 research papers in prestigious professional journals. He is the Regional Editor for the Americas of the journal "Optimization Methods and Software", and serves on the editorial board of three other well known mathematical journals.
Seminars Archive