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.*


Mariya Bondareva, University of Rochester

Suppliers Compliance with Sustainability Requirements Under Poor Legal Enforcement

Wednesday, December 11, 2013

2:00 p.m. - 3:00 p.m.

Mohler Lab #451

Abstract
This work studies the management of compliance with sustainability requirements in a supply chain in a business environment in which monitoring and legal enforcement of penalties is challenging. This situation is relevant to firms operating in developing countries where it is hard to make suppliers pay penalties for poor quality. Because buyers are concerned with quality issues such as nonhazardous chemical content for their products, the questions of enforceability become particularly important. This research uses the framework of a two-level supply chain with one sided moral hazard in which the level of compliance by the supplier is modeled as a defect rate and is not contractible. We model the relationship between the buyer and supplier as a repeated game in which the relationship can be terminated by the buyer if the supplier violates the contract. It is shown that cooperative self-enforcing contracts dominate the relational contracts involving partnership termination. We study the properties of such contracts. As the loss of efficiency can be quite high, other collaborative approaches to compliance with sustainability goals may ultimately be more productive. We offer two-staged contracts as a new tool to reduce eciency loss characteristic to self-enforcing contracts. Such contracts discipline the suppliers by an artificial increase in their search costs. In the first stage, the supplier is forced to have low expected profit per production period. The second stage has higher suppliers expected profit and works as an incentive because of projected future rewards. This approach is new and contributes to the relational contract literature.

Bio-sketch
Mariya Bondareva was born in the USSR. After receiving a diploma with distinction from the Physics and Mathematics lyceum, she entered the East Kazakhstan State Technical University. Mariya graduated with honors and was awarded the degree of Engineer-Economist Systems Analyst in Business Information Systems. Mariya also holds a Candidate of Technical Science degree in Social and Economic Systems Management from Altai State Technical University, Barnaul, Russia. Before her doctoral study in the University of Rochester, she worked as a computer engineer and as a leading specialist in business administration at the Ulba Metallurgical Plant, a part of the state-owned nuclear holding company Kazatomprom. She began doctoral studies in Computer Information Systems at the University of Rochester in 2008 and received a Master of Science in Business Administration in 2011. During her studies, Mariya was an instructor for PhD and MBA level courses. Her research interests include: sustainable supply chains, operations management and service management in IT. In 2013, her research proposal Essays on Managing Quality and Service Standards was unanimously accepted by the dissertation committee at Simon Business School, University of Rochester.


Hoda Bidkhori, Massachusetts Institute of Technology (MIT)

On the Performance of Adaptive Optimization: Theory and Practice

Wednesday, December 4, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab #453

Abstract
We study the performance of linear and piecewise-linear decision rules for adaptive optimization problems based only on the geometry of uncertainty sets. In particular, we show that Minkowski Symmetry and Banach-Mazur distance play a signicant role in determining the power of linear and piecewise-linear decision rules in adaptive optimization problems. We discuss the effectiveness of the proposed decision rules in the context of two-stage inventory control problems. Finally, we introduce a method for evaluating the worst-case performance of a class of distributionally robust optimization problems. This is applied to evaluate the performance of general unbalanced process exibility structures in manufacturing. We derive a simple, tight lower bound for the expected sales for a process flexibility structure known as chaining. Based on two joint works with Dimitris Bertsimas, with David Simchi-Levi and Yehua Wei.

Bio-sketch
Hoda Bidkhori is a postdoctoral associate in Operations Research at MIT. She holds a Ph.D. degree in Applied Mathematics from MIT. Her current research interests lie in decision making under uncertain and data-rich environment, with applications in Flexibility in manufacturing, Logistics and Business analytics. She is a recipient of the Roger Family Prizes at MIT, and Second and Third Prizes in the 8th and 9th International Competition for University Students. She currently serves on the Editorial Board of the Journal of Research and Communications in Mathematics and Mathematical Sciences.


 

Nick Duffield, Rutgers University

What's important? Weighted sampling of the Internet

Tuesday, December 3, 2013

3:00 p.m. - 4:00 p.m.

Mohler Lab #375

Abstract
Sampling large operational datasets such as ISP usage measurements can be effective for reducing storage requirements and execution time, while prolonging the useful life of the data for baselining and retrospective analysis. Sampling needs to mediate between the characteristics data and accuracy need of queries. This talk is about a cost-based formulation to express these opposing priorities, and how it leads to optimal sampling schemes without prior statistical assumptions.

Bio-sketch
Nick Duffield joined Rutgers University as a Research Professor in 2013. Previously he worked at AT&T Labs Research, where he was a Distinguished Member of Technical Staff and an AT&T Fellow. He works on network and data science, particularly the acquisition, analysis and applications of operational network data. He was formerly chair of the IETF Working Group on Packet Sampling, and an associate editor of the IEEE/ACM Transactions on Networking. He is an IEEE Fellow and was a co-recipient of the ACM Sigmetrics Test of Time Award in both 2012 and 2013.


 

Uday V. Shanbhag, Pennsylvania State University

On the solution of Stochastic Optimization and Variational Problems in Imperfect Information Regimes

Wednesday, November 20, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab #453


 

Negar Soheili, Carnegie Mellon University

Elementary Algorithms for Solving Convex Optimization Problems

Friday, November 15, 2013

2:30 p.m. - 3:30 p.m.

Mohler Lab #451

Abstract
A convex feasibility problem is concerned with finding a point in the intersection of convex sets. These problems are fundamental in optimization because any convex optimization problem can be cast in this form. Elementary algorithms are iterative algorithms for solving convex feasibility problems that involve simple operations such as matrix-vector multiplications, vector updates and separation oracles. The simplicity and low computational cost of these algorithms are desirable features for large-scale problems. A major drawback of traditional elementary algorithms is their slow convergence rate. This talk presents new versions of elementary algorithms that are enhanced via smoothing and dilation techniques. These
enhancements yield algorithms that retain the attractive simplicity of elementary algorithms while achieving substantially improved convergence rates.

Bio-Sketch
Negar Soheili is a PhD candidate in Operations Research at the Tepper School of Business, Carnegie Mellon University. She has a Bachelor of Science in Applied Mathematics from University of Tehran. Her research lies at the intersection of machine learning and operations research. In particular, she is currently developing efficient algorithms for large scale convex optimization problems arising in
data analysis.


 

Santanu S. Dey, Georgia Institute of Technology

Analysis of MILP techniques for the Pooling Problem

Wednesday, November 13, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab #453

Abstract
The pooling problem is a challenging non-convex optimization problem that is motivated by refinery processes in the petroleum industry, and also finds application in other areas, such as waste water treatment, emissions regulation and agricultural industry among others. In this talk, we will present an analysis of mixed integer linear programming (MILP) based techniques to solve the
pooling problem. In particular, the talk will focus on three results: (1) We will analyze the quality of dual bounds produced by solving MILP based relaxations of the pooling problem. These MILP relaxations are derived using piecewise-linear approximations for bilinear terms appearing in the model for the pooling problem. (2) We will present an approximation algorithm for the pooling problem and show that unless NP-hard problems have randomized polynomial time algorithms, this algorithm obtains the best possible approximation ratio. (3) Motivated by the approximation algorithm we will present a MILP based heuristic for the pooling problem. This heuristic is guaranteed to provide solutions within a factor of n, where n is the number of output nodes. On medium and large-scale test instances, this MILP based heuristic performs surprisingly well. In particular, it finds the best known solutions for many instances reported in the literature. This is joint work with Akshay Gupte.

Bio-sketch
Santanu S. Dey is currently a Fouts Family Assistant Professor in the Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey holds a Ph.D. in Industrial Engineering from Purdue University. Prior to joining Georgia Tech, he worked as a post-doctoral fellow at the Center for Operations Research and Econometrics (CORE) of the Catholic University of Louvain in Belgium. His research interest is in the area of optimization, specifically mixed integer linear and non-linear programming. Dr. Dey has been the winner of
the INFORMS George Nicholson Student Paper Competition, and has received the IBM Faculty award and the NSF CAREER award.


 

J. Christopher Beck, University of Toronto

Hybridizing Mixed Integer and Constraint Programming

Wednesday, November 6, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab # 453

Abstract
Over the past 10 years there has been a growing body of work at the intersection of mathematical programming as commonly studied in Operations Research and constraint programming (CP) with its origins in Artificial Intelligence (AI) and programming languages. Much of CP's success in solving challenging combinatorial problems comes from the exploitation of inference as embodied in so-called global constraints. This talk provides a brief introduction to CP and then discusses two patterns of hybridization of mixed integer programming (MIP) and CP that have been proposed. I show how these patterns can be used to solve hard combinatorial problems and that they can also inform each other, leading to a more general view of hybridizations centred around the exploitation of problem structure embodied in global constraints. In particular, I propose that the further development of solving techniques associated with global constraints leads to novel research directions in both mathematical and constraint programming.

Bio-sketch
Chris Beck is an Associate Professor and Associate Chair, Research in the Department of Mechanical & Industrial Engineering, University of Toronto. Chris' MSc and PhD degrees both come from the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. Chris then spent three years at ILOG, Paris as a Senior Scientist and Software Engineer on the team responsible for their constraint-based scheduling library (ILOG Scheduler) before spending two years as a Staff Scientist at the Cork Constraint Computation Centre. He returned to Toronto in 2004 to join the Department of Mechanical & Industrial Engineering. Chris' research interests include scheduling, constraint programming, AI planning, reasoning under uncertainty, queueing theory, mixed integer programming, and hybrid optimization techniques. Chris currently serves in an editorial capacity for four journals and one website in AI and OR. He is the President-Elect of the Executive Council for the International Conference on Automated Planning and Scheduling.



Alexander Rakhlin, University of Pennsylvania

Sequential Prediction as an Optimization Problem

Wednesday, October 30, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab # 453

Abstract
A major challenge for machine learning in the next decade is the development of methods that continuously predict and learn from a stream of data. The scale of data and the non-stationary nature of the environment make the prevalent "learn from a batch of i.i.d. data" paradigm inadequate. In this talk, we will formally define the problem of sequential prediction as a (computationally difficult) optimization problem. We will present novel techniques for approximately solving it. These techniques recover many prediction algorithms known in the literature, but also yield new and surprising methods with near-optimal performance. The advances are possible due to a confluence of ideas from empirical process theory, game
theory, and optimization. The field of sequential prediction is largely unexplored, and we hope to present a framework that might be of interest to the optimization community.

Bio-sketch
Alexander Rakhlin is an Assistant Professor at the Department of Statistics and the Department of Computer and Information Science (secondary) at the University of Pennsylvania. He received his bachelors degrees in Mathematics and Computer Science from Cornell University, and doctoral degree from MIT. He was a postdoc at UC Berkeley EECS before joining UPenn, where he is a co-director of the Penn Research in Machine Learning (PRiML) center. His research is in machine learning, with an emphasis on statistics and computation.


Leo Liberti, IBM Research and Ecole Polytechnique

Mathematical Programming: Turing-completeness and applications to algorithmic analysis

Wednesday, October 23, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab # 453

Abstract
We provide a new proof of the fact that Mathematical Programming is Turing-complete, and show how it can be useful in the analysis of code, by presenting two applications. The first aims to find hard inputs for given programs. The second finds relaxations of the set of values taken by the program variables during execution, without actually executing the code.

Joint work with Fabrizio Marinelli, Universita Politecnica delle Marche

Bio-sketch
Leo Liberti graduated in Mathematics from Imperial College London and the University of Turin, Italy, and received his Ph.D. in optimization from Imperial College. He was a postdoctoral fellow at Politecnico di Milano, then a professor at Ecole Polytechnique, France. He is now researcher at the IBM "TJ Watson" research center in Yorktown Heights. He puts his efforts in helping to shape two
communities: Mixed-Integer Nonlinear Programming, and Distance Geometry.


Ilya O. Ryzhov, University of Maryland

Approximate Bayesian inference for simulation and optimization

Friday, October 18, 2013

2:30 p.m. - 3:30p.m.

Mohler Lab # 451

Abstract
Bayesian statistical models can be used to represent the beliefs of a decision-maker about an uncertain environment. For example, in revenue management, a seller formulates beliefs about customers' willingness to pay; in energy, we may have a belief about the suitability of a candidate location for a new wind farm. Conjugate priors model the evolution of these beliefs over time as new information is collected, either from stochastic simulation or field experiments. However, there are relatively few of these conjugate models, and they simply do not exist in many problems of interest. We show how approximate Bayesian inference can be used to create computationally tractable, "nearly conjugate" models that optimally
approximate the actual belief distributions and enable the use of anticipatory information collection and optimization policies. We consider two broad problem classes: simulation selection with unknown correlation structures, and Bayesian learning in logistic regression.

Bio-sketch
Ilya O. Ryzhov is an Assistant Professor in the Department of Decision, Operations, and Information Technologies in the Robert H. Smith School of Business, University of Maryland. He received a Ph.D. in Operations Research and Financial Engineering from Princeton University in 2011. His work deals with the collection and valuation of information in stochastic optimization, with applications in non-profit analytics, energy, and operations management.

He is a coauthor of the book Optimal Learning (Wiley, 2012).


Zoltan Horvath, Szechenyi Istvan University, Gyor, Hungary

On the Discovering of Positively Invariant Sets for Differential Equations via Optimization Methods

Wednesday, October 16, 2013

4:00 p.m. - 5:30 p.m.

Mohler Lab # 451

Abstract
For efficient and physically reliable numerical computations for time dependent differential equations it is very important to find positively invariant subsets of the state space and determine time step sizes of the numerical method that guarantee this. In this talk, we present the state-of-the-art theory and novel approaches beyond it to find positively invariant sets and the suitable time step sizes via optimization techniques.

Bio-sketch
Dr. Zoltan Horvath is the chair of the Department of Mathematics and Computational Sciences at Szechenyi Istvan University. He received his PhD and habilitation from ELTE University Budapest. His research interest is mainly
on numerical methods for differential equations and several topics in applied mathematics.


Immanuel M. Bomze, University of Vienna

Title: Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

Wednesday, September 25, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab # 453

Abstract

For all-quadratic problems (without any linear constraints), it is well known that the semidefinite relaxation coincides basically with the Lagrangian dual problem. Here we study a more general case where the constraints can be either quadratic or linear. To be more precise, we include explicit sign constraints on the problem variables, and study both the full Lagrangian dual as well as the Semi-Lagrangian
relaxation. We show that the stronger Semi-Lagrangian dual bounds coincide with the ones resulting from copositive relaxation. This way, we arrive at a full hierarchy of tractable conic bounds stronger than the usual Lagrangian dual (and thus than the SDP) bounds. We also specify sucient conditions for tightness of the Semi-Lagrangian (i.e. copositive) relaxation and show that copositivity of the slack
matrix guarantees global optimality for KKT points of this problem.

Bio-sketch

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 scientific 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 scientific 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 scientific 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.


Stephen Becker, IBM T.J. Watson Research Center

Title: The interplay of optimization and randomized linear algebra

Wednesday, September 18, 2013

4:00 p.m. - 5:00 p.m.

Mohler Lab #453

Abstract

The first part of this talk reviews some modern randomized linear algebra techniques. The goal of these methods is to perform approximate matrix multiplication or matrix factorizations (e.g., SVD) with lower computational cost than conventional methods. We then discuss using these methods inside optimization algorithms. The two main questions are (1) is the
randomized approach faster, and (2) does the error from the randomized linear algebra affect the optimization algorithms? There are powerful recent results that bound the error of the linear algebra, but they are rarely applied to obtain rigorous guarantees for an optimization algorithm. We also touch on stochastic gradient descent, and apply all of these topics to some specific matrix recovery problems, such as quantum state tomography and matrix completion of the Netflix dataset.

Bio-sketch

Stephen Becker received his B.A. degrees in mathematics and in physics
from Wesleyan University in 2005, and his Ph.D. degree in Applied &
Computational Mathematics from the California Institute of Technology in 2011. From 2011 to 2013 he was a postdoctoral fellow at the Jacques-Louis Lions lab at Paris 6 thanks to a fellowship from the Fondation Sciences Mathematiques de Paris. Currently he is the Goldstine postdoctoral fellow at IBM's T. J. Watson Research Center in Yorktown Heights NY. His research interests are in large-scale optimization methods for signal processing and machine learning.


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.

Power Point slides

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