# Seminars presented Fall 2011

### 09/08/11 RUTCOR Colloquium - 1:30PM

Speaker:Kaz Makino
Affiliation:University of Tokyo
Title: Robust Independence Systems

Abstract: An independence system F is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number a> 0, a set X in F is said to be a-robust if for any k, it includes an a-approximation of the maximum k-independent set, where a set Y in F is called k-independent if the size |Y| is at most k. In this paper, we show that every independence system has a 1/sqrt{mu(F)} robust independent set, where mu(F) denotes the exchangeability of F. Our result contains a classical result for matroids and the ones of Hassin and Rubinstein for matchings and Fujita, Kobayashi, and Makino for matroid 2-intersections, and provides better bounds for the robustness for many independence systems such as b-matchings, hypergraph matchings, matroid p-intersections, and unions of vertex disjoint paths. Furthermore, we provide bounds of the robustness for nonlinear weight functions such as submodular and convex quadratic functions. We also extend our results to independence systems in the integral lattice with separable concave weight functions.
This is a joint work with Naonori Kakimura.

### 09/15/11 RUTCOR Colloquium - 1:30PM

Speaker:Khaled Elbassioni
Affiliation:Max-Planck-Institut fur Informatik, Saarbrucken
Title: Tree-constrained Matching

Abstract: We consider the following Tree-Constrained Bipartite Matching problem: Given two rooted trees $T_1=(V_1,E_1)$, $T_2=(V_2,E_2)$ and a weight function $w: V_1\times V_2 \mapsto \mathbb{R}_+$, find a maximum weight matching $\mathcal{M}$ between nodes of the two trees, such that none of the matched nodes is an ancestor of another matched node in either of the trees. This generalization of the classical bipartite matching problem appears, for example, in the computational analysis of live cell video data. We show first that the problem is APX-hard and thus, unless P= NP, admits no polynomial-time approximation scheme. We then give a $2$-approximation algorithm based on a combination of the local ratio technique and a careful use of the structure of basic feasible solutions of a natural LP-relaxation, which we also show to have an integrality gap of $2-o(1)$.
Generalizing further, we consider a variant of the problem, where trees are replaced by partially ordered sets (posets). We show that the local ratio technique gives a $2k\rho$-approximation for the $k$-dimensional matching generalization of the problem, in which the maximum number of incomparable elements below (or above) any given element in each poset is bounded by $\rho$. We also give an inapproximability result showing that this dependence on $\rho$ is most likely unavoidable.

### 09/21/11 Special MSIS/RUTCOR Joint Seminar - 2:00PM

Speaker: Professor Volodymyr Babich
Affiliation: Georgetown University
Title: Decentralized Supply Risk Management: Competition vs.            Diversification with Asymmetric Information

### 09/22/11 RUTCOR BrownBag - 12 Noon

Speaker:Christina Achampong
Affiliation: Enterprise Operations Research, Modeling and Simulation
National Security Agency
Title: Summer Program for Operations Research Technology at             NSA

Abstract: The National Security Agency’s (NSA) Office of Operations Research, Modeling and Simulation applies scientific and quantitative methods to help NSA and other Intelligence Community organizations better understand and find solutions to their operational problems. The Summer Program for Operations Research Technology (SPORT) offers U.S. citizen graduate students the opportunity to apply their academic knowledge in a stimulating professional environment. As a SPORT intern you will work closely with full-time analysts applying the technical skills you’ve learned in college to challenging real-world problems of your choice. Learn more about SPORT as we show a brief video on NSA followed by a discussion of program details.

### 09/28/11 Special MSIS/RUTCOR Joint Seminar - 2:00PM

Speaker: Professor Van-Anh Truong
Affiliation: Columbia University
Title: Multi-Dimensional Approximation Algorithms for Capacity-            Expansion Problems

Abstract: We develop multi-dimensional balancing algorithms to compute provably near-optimal capacity-expansion policies. These are the first approximation algorithms for multi-machine, multi-product systems facing stochastic, non-stationary and correlated demands. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost no more than twice that of an optimal policy. We overcome the curse of dimensionality by introducing novel separable schemes to decompose the lost-sales cost to the system by machine types. We make the assumptions of minimal inventory and lost sales. We treat two different models for making production decisions at each time instant: Monotone Production and Revenue-Maximizing Production.

### 10/06/11 RUTCOR Colloquium - 1:30PM

Affiliation: Yeshiva University, New York
Title: Ordered Direct Implicational Basis of a Finite Closure System
This is joint work with J.B.Nation (University of Hawaii) and Robert Rand (undegraduate of Yeshiva College).

Abstract: Closure system on a nite set is a unifying concept in logic pro- gramming, relational data bases and knowledge systems. It can also be pre- sented in the terms of nite lattices, and the tools of economic description of a nite lattice have long existed in lattice theory. We present this approach by describing the so-called D-basis and introducing the concept of ordered direct basis of an implicational system. A direct basis of a closure operator, or an implicational system, is a set of implications that allows one to compute the closure of an arbitrary set by a single iteration. This property is preserved by the D-basis at the cost of following a prescribed order in which implications will be attended.

One can extract the D-basis from any direct unit basis S in time polynomial in the size s(S), and it takes only linear time of the cardinality of the D-basis to put it into a proper order. We produce examples of closure systems on a 6-element set, for which the canonical basis of Duquenne and Guigues is not ordered direct.

We ran test comparison for D-basis versus canonical direct and Duquenne- Guigues bases, and analyzed the advantages of direct basis algorthim versus forward chaining algorithm used in logic programming.

### 10/13/11 Special MSIS/RUTCOR Joint Seminar - 1:30 PM

Speaker:  Professor Steve Marcus
Affiliation: University of Maryland - College Park
Location:   1 Washington Park #1027
Video Conference at Levin # 130
Title: A Model Reference Adaptive Search Method for Global                 Optimization
This is joint work with Jiaqiao Hu and Michael Fu.

Abstract: We Model Reference Adaptive Search (MRAS) is a randomized search method for solving global optimization problems. The method works with a parameterized probabilistic model on the solution space and generates at each iteration a group of candidate solutions. These candidate solutions are then used to update the parameters associated with the probabilistic model in such a way that the future search will be biased toward the region containing high quality solutions. The parameter updating procedure in MRAS is guided by a sequence of implicit probabilistic models called reference models. We show that the model reference framework can be used to describe the recently proposed cross-entropy (CE) method for optimization and study its properties. We prove global convergence of the proposed algorithm in both continuous and combinatorial domains, and we carry out numerical studies to illustrate the performance of the algorithm. At the end of the talk, we will describe recent work (with Enlu Zhou and Yongqiang Wang) utilizing particle filtering and evolutionary games to develop related classes of global optimization algorithms.

### 10/20/11 RUTCOR BrownBag - 12:00 Noon

Speaker:Jian Yang
Affiliation:Dept. of Mechanical & Industrial Engineering, NJIT
Title: Connections between Finite- and Infinite-player Games: Normal- and Extended-form Analyses

Abstract: We establish two links between finite-player games and their corresponding nonatomic games (NGs). In a normal-form game setting, we show that an NG's equilibrium can generate near equilibrium payoffs for large finite games whose player types are sampled from the NG's signature distribution. In an extended-form game setting involving individual player states that bridge players' past actions with their future gains, we show that large finite games can use an equilibrium of the NG counterpart to reap close-to-best payoffs. The action plan recommended by the NG equilibrium is prominent in that it is blind to the current player's observation of its immediate surrounding. These links especially the latter one have potential to help simplify the analysis of competitive situations with many players.

### 10/27/11 RUTCOR BrownBag - 12 Noon

Affiliation: RUTCOR and School of Business
Title: An Algebraic view of sum-of-squares and their semidefinite representability, with applications
This is joint work with David Papp of Northwestern University

Abstract: In the past fifteen years it has been recognized that the set of multivariate polynomials of total degree at most d, which are sum-of-squares of other polynomials, can be expressed as an image of the set of positive semidefinite matrices. As a result, recognition and optimization problems for such sets is reducible to semidefinite programming (SD-representable). This fact is exploited by many authors to design approximation algorithms for hard combinatorial problems, to recognize stability and design filters in control and systems theory and signal processing, and to estimate unknown functions with shape constraints in statistical learning theory.
In this talk we show that the SD-representability of "sum-of-squares" goes far beyond polynomials and in fact is true in any algebra. In particular, let A be a vector space with an additional bilinear binary operation on its elements, where the product a.b is in another vector space B. Then we show that the set of elements in B of the form a_1.a_1 + ... + a_n.a_n, for any integer n, is SD-representable. Using common algebraic notions such as isomorphism, linear isomorphism, direct sums, and tensor products we show that new and rich classes of convex cones are SD-representable.
In the last part of the talk, time permitting, we will review some concrete applications; among them are: computing the smallest volume ball or ellipsoid containing a finite set of space curves, optimization of certain symmetric functions of eigenvalues of matrix-valued polynomials, and estimation of unknown functions with shape constraints from noisy data.

### 11/02/11 Special MSIS/RUTCOR Joint Seminar - 2:00PM

1 Washington Park #1027, Video conference at Levin Room 130

Speaker: Professor Nick Sahinidis
Affiliation: Carnegie Mellon University
Title: Optimization Without Algebraic Models: Algorithms, Software, and Applications

Abstract: Fueled by a growing number of applications in science and engineering, the development of algorithms for solving optimization problems in the absence of algebraic models has found renewed interest in recent years. The topic is often referred to as derivativefree optimization and black-box optimization. In this talk, we first present a review of algorithms and systematic comparison of over twenty related software implementations using a test set of over 500 problems. Then, we propose a new family of local and global optimization algorithms for this class of problems, and summarize computational experience from a variety of applications.

### 11/09/11 Special MSIS/RUTCOR Joint Seminar - 2:00PM

1 Washington Park #1027, Video conference at Levin Room 130

Speaker: Professor Jim Calvin
Affiliation: Department of Computer Science
New Jersey Institute of Technology
Title: Complexity of Global Optimization

Abstarct: How hard is it to approximate the minimum of a continuous function? Worst-case complexity bounds require assumptions such as unimodality that may not be reasonable for some practical optimization problems. If the function is only known to be continuous, or differentiable of some order, then a worst-case analysis is not useful. Instead, one seeks algorithms that give estimates with small error on average while accepting that for some functions the error will be large. In this talk I will describe average-case complexity bounds for global optimization for a family of Gaussian probabilities on univariate functions with varying degrees of smoothness. The lower bounds hold for all algorithms that use function or derivative evaluations to approximate the minimum; any algorithm that produces a given average error must require, on average, a certain number of function or derivative evaluations. Upper complexity bounds are obtained by constructing and analyzing specific optimization algorithms.

### 11/10/11 RUTCOR BrownBag - 12 Noon

Speaker:  Honggang Wang
Affiliation: Industrial & Systems Engineering
Title: Retrospective optimization for oil field development under             uncertainty

Abstract: In oil field development, because well costs can be extremely high, it is essential that wells be drilled in productive (optimal) locations. The well placement optimization problem is greatly complicated by the fact that the geological model of the subsurface is highly uncertain. This uncertainty can be addressed by considering many possible realizations of the subsurface and evaluating well performance (using a reservoir flow simulator) for each model. This can be prohibitively time consuming if all evaluations of the objective function entail simulation of all realizations.
In order to make such optimizations tractable, we introduce and apply retrospective optimization (RO), originally developed for discrete stochastic systems. Rather than consider all realizations at each optimization step, RO solves a convergent sequence of sample-path subproblems with increasing numbers of realizations. Numerical results based on three well placement problems demonstrate that RO handles reservoir uncertainty efficiently and finds solutions that provide significant increases in oil production.

### 11/28/11 Special Joint ISE/RUTCOR Seminar - 1:30PM

Lecture Hall, First Floor, CoRE Building

Speaker: Bill Cook
Affiliation: Industrial & Systems Engineering, Georgia Tech
Title: The Traveling Salesman Problem: A Blueprint for
Optimization

Abstract: Given a list of cities along with the cost of travel between each pair of them, the traveling salesman problem is to find the cheapest way to visit them all and return to your starting point. Easy to state, but difficult to solve. In this talk we discuss the problem's history, applications, and computation, laying out a blueprint for future work in optimization and the practical solution of large-scale, possibly intractable, decision models.

### 12/01/11 RUTCOR Colloquium - 1:30 PM

Speaker: Giovanni Felici
Affiliation: Istituto di Analisi dei Sistemi ed Informatica
Consiglio Nazionale delle Ricerche, Rome
Title: Robust Heuristics for Data Discretization and Feature Selection in Supervised Learning

Abstract: We consider two connected problems that arise in supervised learning: data discretization and integer feature selection. For both problems we present some mathematical formulation and discuss the related optimization problems. Given their NP-completeness and the large size of the instances that are to be solved in practical applications, we propose for both problems an integrated heuristic solution strategy based on greedy randomization and alternate search. The strategy has been implemented and successfully tested on real and simulated data.

We have two Seminar Series: Brown Bag Talks and RUTCOR Colloquia.
Brown Bag Talks are usually on Thursdays, 12:00-1:00, in the RUTCOR lounge. Pizza is served but feel free to bring your own lunch. The Brown Bag Series usually host speakers from the RUTCOR community.
RUTCOR Colloquia are usually held Thursdays, 1:30-2:30 PM, in the Seminar Room or Room 139. The RUTCOR Colloquia feature speakers from outside the RUTCOR community.

#### Research Areas

Discrete and Combinatorial Optimization
Linear and Nonlinear Programming
Stochastic Optimization
Boolean methods in Operations Research
Queuing Theory
Logical Analysis of Data