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
Abstract: We study a buyer’s strategic use of a dual-sourcing option when facing suppliers possessing private information about their disruption likelihood. We solve for the buyer’s optimal procurement contract. We show that the optimal contract can be interpreted as the buyer choosing between diversification and competition benefits. Better information increases diversification benefits and decreases competition benefits. Therefore, with better information the buyer is more inclined to diversify. Moreover, better information may increase or decrease the value of the dual-sourcing option, depending on the buyer’s unit revenue: for large revenue, the buyer uses the dual sourcing option for diversification, the benefits of which increase with information; for small revenue, the buyer uses the dual sourcing option for competition, the benefits of which decrease with information. Surprisingly, as the reliability of the entire supply base decreases, the buyer may stop diversifying under asymmetric information (to leverage competition), while it would never do so under symmetric information. Finally, we analyze the effect of codependence between supply disruptions. We find that lower codependence leads the buyer to rely less on competition. Because competition keeps the information costs in check, a reduction in supplier codependence increases the buyer’s value of information. Therefore, strategic actions to reduce codependence between supplier disruptions should not be seen as a substitute for learning about suppliers’ reliabilities. The papers are available at http://ssrn.com/abstract=1275110 and http://ssrn.com/abstract=1616969.
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
Speaker: Kira Adaricheva
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
Speaker: Farid Alizadeh
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.