Sunday Oct 11
| Delete | | | 08:00 - 09:30 : Stochastic Control and Optimization |
| Chair: | Yang Wang,Stanford
University, Packard Electrical Engineering, 350 Serra Mall, Stanford CA
94305, United States of America, yw224@stanford.edu
| Title: | Singular Stochastic Control and Composite Markov Processes | | Lead: | Xiren Cao,Professor,
Hong Kong University of Science and Technology, Clear Water Bay,
Kowloon, Hong Kong, Hong Kong - PRC, eecao@ust.edu.hk
| | Abstract: | We
propose a composite model for Markov processes. The state space of a
composite Markov process consists of two parts, J and J-. When the
process is in J-, it evolves like a continuous-time Levy process; and
once the process enters J, it makes a jump instantly like a
discrete-time Markov chain. The composite Markov process provides a new
model for singular stochastic control problem, and we show that this
problem can be solved using a direct-comparison method. | | | Title: | Computationally Tractable Performance Bounds for Constrained Linear Stochastic Control | | Lead: | Yang Wang,Stanford
University, Packard Electrical Engineering, 350 Serra Mall, Stanford CA
94305, United States of America, yw224@stanford.edu
| | Abstract: | We
present computational lower bounds on performance for constrained
linear stochastic control. Our method involves solving a semidefinite
program, a convex optimization problem which we can solve efficiently.
Numerical experiments show that the lower bound obtained by our method
is often close to the performance achieved by suboptimal control
policies. As a by-product, our bound yields approximate value functions
that can be used as control Lyapunov functions for suboptimal control
methods. | | | Title: | Structural Properties of the Value of Information in Single-Stage Ranking and Selection | | Lead: | Peter Frazier,Assistant Professor, Cornell University, Rhodes Hall, Ithaca NY 14853, United States of America, pf98@cornell.edu
| | Abstract: | Within
the Bayesian ranking and selection problem with independent normal
priors and independent normal sampling noise, we consider the expected
value of information obtained from a non-sequential sampling
allocation. This quantity is known to be a non-concave function of the
sampling allocation, which makes finding the optimal allocation
difficult. Nevertheless, this function possesses a number of structural
properties. We discuss these properties and their application. | | | Title: | Optimal Learning On A Graph | | Lead: | Ilya Ryzhov,Princeton University, Princeton NJ 08540, United States of America, iryzhov@princeton.edu
| | Co-Author: | Warren Powell,Professor, Princeton University, Sherrerd Hall 230, Princeton NJ 08544, United States of America, powell@princeton.edu
| | Abstract: | Consider
a stochastic path-finding problem on a graph where the distributions of
the arc costs are unknown. By sequentially measuring individual edges,
we can refine Bayesian estimates of the arc costs. Our goal is to
allocate measurements in order to efficiently learn about the optimal
solution to the path-finding problem. We propose a knowledge gradient
policy that is easy to compute, with certain desirable theoretical
properties, and performs competitively against other learning
strategies. | | |
|
Delete | | | 08:00 - 09:30 : Computational Optimization Methods and Applications |
| Chair: | Jiawang Nie,UCSD, 9500 Gilman Drive, La Jolla\, United States of America, njw@math.ucsd.edu
| Title: | An Affine-scaling Interior-point Method for Continuous Knapsack Constraints | | Lead: | Hongchao Zhang,Department of Mathematics, Louisiana State University, Baton Rouge LA, hozhang@math.lsu.edu
| | Abstract: | A
gradient based affine-scaling algorithm for continuous
knapsack constraints will be presented. This algorithm has the property
that each iterates lie in the interior of the feasible set and is more
suitable for large dimensional optimization problems where the Hessian
of the objective function is a large, dense, and possibly
ill-conditioned matrix. Global and local linear convergence of the
algorithm will be discussed. Numerical results will be also reported. | | | Title: | Solving Graph Bisection Minimization Problems using Convex Quadratic Relaxations | | Lead: | Dzung Phan,University of Florida, 358 Little Hall, P.O. Box 118105, Gainesville FL 32611-8105, United States of America, dphan@ufl.edu
| | Co-Author: | William Hager,University
of Florida, 358 Little Hall, P.O. Box 118105, Gainesville FL
32611-8105, United States of America, hager@math.ufl.edu
| | Abstract: | We
present an exact algorithm for solving the node and edge weighted graph
partitioning problem. The algorithm is based on a continuous quadratic
formulation of the problem. Necessary and sufficient optimality
conditions for a local minimizer of the quadratic program are
introduced. Lower bounds for the branch and bound algorithm are
obtained by replacing the concave part of the objective function by the
best affine underestimator. Numerical results show the effectiveness of
our method. | | | Title: | A Convergence Theorem for Solving the SQP System in SSM | | Lead: | Ning Guo,Student, University of Florida, Gainesville FL, guoning@ufl.edu
| | Co-Author: | William Hager,Professor, University of Florida, Gainesville FL, hager@ufl.edu
| | Abstract: | SSM(sequential
subspace method) is an iterative method used to solve the trust region
subproblem. A convergence theorem is developed concerning how precisely
we should solve the SQP(sequential quadratic programming) system in
each iteration in order to obtain an at least linear convergence for
the non-degenerate case. We shall look at some numerical results.
| | |
|
Delete | | | 08:00 - 09:30 : Interior-point Methods |
| Chair: | Samir Elhedhli,University of Waterloo, 200 University Avenue West, Waterloo ON N2L 3G1, Canada, elhedhli@uwaterloo.ca
| Title: | Bi-parametric Convex Quadratic Optimization | | Lead: | Tamas Terlaky,Professor,
Chair, Lehigh University, Department ISE, H. Mohler Lab,, 200 West
Packer Ave, Bethlehem PA 18015, United States of America,
terlaky@lehigh.edu
| | Co-Author: | Alireza Ghafari Hadigheh,Professor, Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, Iran, hadigheha@azaruniv.edu
| | | Oleksandr Romanko,PhD Candidate, McMaster University, 1280 Main Street West, Hamilton ON L8S4K1, Canada, romanko@mcmaster.ca
| | Abstract: | We
consider the Convex Quadratic Optimization problem with simultaneous
perturbation in the right-hand-side of the constraints and the linear
term of the objective function with different parameters. The regions
with invariant optimal partitions are investigated as well as the
behavior of the optimal value function on the regions. Identifying
these regions can be done in polynomial time in the output size. An
algorithm for identifying all invariancy regions is presented. | | | Title: | Interior-Point Methods for Integer Programming: The ACCPM Approach | | Lead: | Samir Elhedhli,University of Waterloo, 200 University Avenue West, Waterloo ON N2L 3G1, Canada, elhedhli@uwaterloo.ca
| | Abstract: | This
talk highlights the use of interior point methods in solving integer
programming through the Analytic Centre Cutting Plane Method (ACCPM).
Heuristic, Branch-and-price, branch-and-cut, and Benders decomposition
algorithms will be presented that compete with LP-based approaches. | | | Title: | An L1 Elastic Interior-Point Method for MPCCs | | Lead: | Zoumana Coulibaly,Phd
Student, Ecole Polytechnique de Montreal and GERAD, 2500, chemin de
Polytechnique, Montreal Qc h2e2g5, Canada, zoumana.coulibaly@polymtl.ca
| | Abstract: | Our
interior-point algorithm consist of an elastic formulation of the
L1-penalty merit function for mathematical programs with
complementarity constraints. The method naturally converges, at a
sub-quadratic local convergence rate, to a strongly stationary point or
delivers a certificate of degeneracy without recourse to second-order
intermediate solutions. Numerical results on a standard test set
illustrate the efficiency and robustness of the approach. | | | Title: | Solving Unconstrained Nonlinear Programs with ACCPM | | Lead: | Ahad Dehghani,McGill University, 1001 Sherbrooke west, Montreal H3A 1G5, Canada, ahad.dehghani@mcgill.ca
| | Co-Author: | Jean-louis Goffin,McGill University, 1001 Sherbrooke west, Montreal H3A 1G5, Canada, jean-louis.goffin@mcgill.ca
| | | Dominique Orban,Ecole Polytechnique de Montréa, Mathematics and Industrial Engineering D, Montreal Qc, Canada, dominique.orban@gerad.ca
| | Abstract: | ACCPM
and proximal ACCPM are well known techniques for convex programming
problems. We propose a sequential convex programming method based on
ACCPM and convexification techniques to tackle unconstrained problems
with a non-convex objective function.
| | |
|
Delete | | | 11:00 - 12:30 : Gradient Algorithms for Large Scale Convex Optimization |
| Chair: | Peter Richtarik,University
of Edinburgh, James Clerk Maxwell Building, The King's Buildings,
Edinburgh EH9 3JZ, United Kingdom, peter.richtarik@uclouvain.be
| Title: | Primal-Dual Gradient Methods for Structured Convex Problems | | Lead: | Peter Richtarik,University
of Edinburgh, James Clerk Maxwell Building, The King's Buildings,
Edinburgh EH9 3JZ, United Kingdom, peter.richtarik@uclouvain.be
| | Co-Author: | Yurii Nesterov,Catholic University of Louvain, CORE/INMA, 34 Voie du Roman Pays, Louvain-la-Neuve 1348, Belgium, yurii.nesterov@uclouvain.be
| | Abstract: | In
this work we develop and analyze an algorithm for minimizing a linear
function over a simple convex compact set intersected with an affine
subspace. We construct a primal-dual convex reformulation of the
original problem with optimal value zero and analyze new gradient
methods for minimizing convex functions with known optimal value. A
special case of our algorithm is the subgradient method at one extreme
and the level method at the other. | | | Title: | Approximate and Restarted Estimate Sequences Schemes | | Lead: | Michel Baes,ETH, IFOR, Rämistrasse101, Zurich 8092, Switzerland, michel.baes@ifor.math.ethz.ch
| | Abstract: | Estimate sequences are provably the fastest gradient method for smooth
convex problems. At every iteration, one must compute the objective
gradient and solve two optimization problems. We determine how
accurately those computations have to be done to avoid error
propagations. Several variants of estimate sequence schemes will also
be analyzed, including different restarting strategies.
| | | Title: | AdaBoost - Nothing Else Than a Mirror Descent Algorithm? | | Lead: | Michael Buergisser,ETH, IFOR, Rämistrasse101, Zurich 8092, Switzerland, michael.buergisser@ifor.math.ethz.ch
| | Co-Author: | Michel Baes,ETH, IFOR, Rämistrasse101, Zurich 8092, Switzerland, michel.baes@ifor.math.ethz.ch
| | Abstract: | Freund and Schapire introduced AdaBoost, a standard scheme in Machine
Learning, in the late nineties. Mirror descent methods are due to
Nemirovski and Yudin and belong to the class of subgradient schemes.
We show that AdaBoost coincides with a well-chosen mirror descent
algorithm. For this, we define an appropriate objective function and
interpet AdaBoost's weak learner as an oracle providing approximate
stochastic subgradients.
| | |
|
Delete | | | 13:30 - 15:00 : Some Advances in Conic Optimization |
| Chair: | Mohammad Oskoorouchi,College
of Business Administration, California State University San Marcos, 333
S. Twin Oaks Valley Road, San Marcos CA 92096, United States of
America, moskooro@csusm.edu
| Title: | An Interior Point Constraint Generation Method for Semi-infinite Linear Programming | | Lead: | Mohammad Oskoorouchi,College
of Business Administration, California State University San Marcos, 333
S. Twin Oaks Valley Road, San Marcos CA 92096, United States of
America, moskooro@csusm.edu
| | Co-Author: | Hamid Ghaffari,University of Toronto, 5 King's Collage Rd., Toronto, Canada, h.ghaffari@utoronto.ca
| | | Tamas Terlaky,Professor,
Chair, Lehigh University, Department ISE, H. Mohler Lab,, 200 West
Packer Ave, Bethlehem PA 18015, United States of America,
terlaky@lehigh.edu
| | Abstract: | We
present an interior point constraint generation algorithm for
semi-infinite linear optimization and prove that the algorithm
converges to an $\varepsilon$-solution after a finite number of
constraints is generated. We implement our algorithm to solve
second-order cone optimization (SOCO) problems and compare our
numerical results with that of SeDuMi and show that our method
outperforms classical primal-dual interior point methods on a class of
large-scale SOCO problems. | | | Title: | Full-Newton Step Polynomial-time Methods for LO Based on Locally Self-concordant Barrier Functions | | Lead: | Kees Roos,TU Delft, Mekelweg 4, Delft, Netherlands, C.Roos@tudelft.nl
| | Co-Author: | G. Lesaja,College of Science and Technology, Georgia Southern University, United States of America, Goran@GeorgiaSouthern.edu
| | | H. Mansouri,Department of Mathematical Science, Shahrekord University, Iran, HMansory@yahoo.com
| | Abstract: | Recently,
several interior-point methods were introduced by using barrier
functions that are based on kernel functions. These barrier functions
are not self-concordant.
Near the central path, however, they behave as being self-concordant.
Using this we prove that for full-Newton step variants of these methods
the iteration bound is the currently best known bound for LO.
| | | Title: | Relationships Among Some Geometric Measures of Convex Cones | | Lead: | Levent Tuncel,Professor,
University of Waterloo, Dept. Combinatorics and Optim., 200 Unversity
Avenue, West, Waterloo ON N2L3G1, Canada, ltuncel@math.uwaterloo.ca
| | Co-Author: | Hugo Lara,Universidad CLA, Apdo 400., Barquisimeto 3001, Venezuela, hugol@ucla.edu.ve
| | Abstract: | We
study geometric measures of convex cones and present various
relationships among the width, the norm approximation coefficient,
Caratheodory number and Goffin-Cheung-Cucker measure of convex cones. | | | Title: | An Active Set Algorithm for Semidefinite Programming | | Lead: | Kartik Sivaramakrishnan,Senior
Research Associate, Axioma, Inc., 8800 Roswell Road, Building B, Suite
295, Atlanta GA 30350, United States of America, kksivara@gmail.com
| | Co-Author: | John Mitchell,Professor,
Rensselaer Polytechnic Institute, Department of Mathematical Sciences,
110 Eighth Street, Troy NY 12180, United States of America,
mitchj@rpi.edu
| | Abstract: | We
develop an active set framework for solving approximately solving large
scale semidefinite programming problems (SDPs) as a sequence
of smaller semidefinite programs in every iteration. We will highlight
the features of our algorithm and also present some of our preliminary
computational results. | | |
|
Delete | | | 13:30 - 15:00 : ICS Prize Winners |
| Chair: | S. Raghavan,Associate
Professor, University of Maryland, University of Maryland, College Park
MD, United States of America, raghavan@umd.edu
| Title: | An Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming | | Lead: | Andreas Wächter,PhD,
IBM T.J. Watson Research Center, Department of Mathematical Sciences,
P.O. Box 218, Yorktown Heights NY 10598, andreasw@watson.ibm.com
| | Co-Author: | Lorenz Biegler,Professor,
Carnegie Mellon University, Department of Chemical Engineering, 5000
Forbes Avenue, Pittsburgh PA 15213, United States of America,
lb01@andrew.cmu.edu
| | Abstract: | We present an algorithm for large-scale nonlinear continuous
optimization, together with real-life applications, such as the tuning
of transistors in digital circuits, modeling and design of chemical
processes and optimal control of nonlinear dynamic systems. We will
also present some recent developments of the algorithm, including
parametric sensitivity of NLP solutions and the use of iterative
linear solvers. An implementation of this algorithm ("Ipopt") is
available as open source. | | | Title: | A Line Search Multigrid Method for Large-Scale Nonlinear Optimization (Winning Paper) | | Lead: | Zaiwen Wen,NSF
Math Institutes’ postdoc, IPAM, University of California, Los Angeles
and Rice University, United States of America, zw2109@columbia.edu
| | Co-Author: | Donald Goldfarb,Professor, Columbia University, New York, New York, United States of America, goldfarb@columbia.edu
| | Abstract: | We
present a line search multigrid method for solving discretized versions
of general unconstrained infinite dimensional optimization problems. At
each iteration on each level, the algorithm computes either a “direct
search” direction on the current level or a “recursive search”
direction from coarser level models. Introducing a new condition that
must be satisfied by a backtracking line search procedure, the
“recursive search” direction is guaranteed
to be a descent direction. Global convergence is proved under fairly
minimal requirements on the minimization method used at all grid
levels. Using a limited memory BFGS quasi- Newton method to produce the
“direct search” direction, preliminary numerical experiments show that
our line search multigrid approach is promising. | | | Title: | The Knowledge-Gradient Policy for Correlated Normal Beliefs (Honorary Mention) | | Lead: | Peter Frazier,Assistant Professor, Cornell University, Rhodes Hall, Ithaca NY 14853, United States of America, pf98@cornell.edu
| | Co-Author: | Savas Dayanik,Department of Operations Research and Financial Engineering, Princeton University, Princeton NJ 08544, sdayanik@princeton.edug
| | | Warren Powell,Professor, Princeton University, Sherrerd Hall 230, Princeton NJ 08544, United States of America, powell@princeton.edu
| | Abstract: | We
consider a Bayesian ranking and selection problem with independent
normal rewards and a correlated multivariate normal belief on the mean
values of these rewards. Because this formulation of the ranking and
selection problem models dependence between alternatives'
mean values, algorithms may utilize this dependence to perform
effciently even when the number of alternatives is very large. We
propose a fully sequential sampling policy called the
knowledge-gradient policy, which is provably optimal in some special
cases and has bounded suboptimality in all others. We then demonstrate
how this policy may be applied to effciently maximize a continuous
function on a continuous domain while constrained to a xed number of
noisy measurements | | | Title: | Appointment Scheduling with Discrete Random Durations (Honorary Mention) | | Lead: | Mehmet Begen,Richard
Ivey School of Business, University of Western Ontario, 1151 Richmond
St. N., London ON N6A 3K7, Canada, mbegen@ivey.uwo.ca
| | Co-Author: | Maurice Queyranne,Sauder
School of Business, University of British Columbia, 2053 Main Mall,
Vancouver BC, Canada, maurice.queyranne@sauder.ubc.ca
| | Abstract: | We
consider the problem of determining an optimal appointment schedule for
a given sequence of jobs (e.g., medical procedures) on a single
processor (e.g., operating room, exami- nation facility, physician), to
minimize the expected total underage and overage costs when each job
has a random processing duration given by a joint discrete probability
distribution.
Simple conditions on the cost rates imply that the objective function
is submodular and L-convex. Then there exists an optimal appointment
schedule which is integer and can be found in polynomial time. Our
model can handle a given due date for the total processing (e.g., end
of day for an operating room) after which overtime is incurred, and
no-shows and some emergencies. | | | Title: | ICS Prize Session | | Abstract: | The winners of the 2009 ICS Prize and the 2009 ICS Student
Paper Award present their award-winning work. | | |
|
Delete | | | 13:30 - 15:00 : Convex Hull Approximations for Integer and Global Optimization |
| Chair: | Suvrajeet Sen,Professor, The Ohio State University, 1971 Neil Ave, Columbus OH 43210, United States of America, sen.22@osu.edu
| Title: | On Polytopes Associated with Products of Discrete Variables | | Lead: | Warren Adams,Professor, Clemson University, Martin Hall, Clemson SC 29634, United States of America, wadams@clemson.edu
| | Co-Author: | Stephen M Henry,Department of Mathematical Sciences, Clemson University, Clemson SC, smhenry@clemson.edu
| | Abstract: | Linearizations
of quadratic binary terms have been well-studied. However, little is
known for the discrete case. We characterize desirable extreme point
traits of discrete polytopes, and establish fundamental results
relative to dimension and facial structure. Convex hull representations
are obtained for special instances, and partial such results in general. | | | Title: | Exploiting Multilinearity in Global Optimization Relaxations | | Lead: | Mohit Tawarmalani,Associate
Professor, Krannert Graduate School of Management of Purdue University,
4026, RAWLS Hall, 100, S. Grant, West lafayette IN 47907, United States
of America, mtawarma@purdue.edu
| | Co-Author: | Xiaowei Bao,University of Illinois at Urbana Champaign, xbao2@uiuc.edu
| | | Nick Sahinidis,John
E. Swearingen Professor, Carnegie Mellon University, Department of
Chemical Engineering, Pittsburgh, United States of America,
sahinidis@cmu.edu
| | Abstract: | We
use the convex extensions theory to derive a column-generation
algorithm for generating facets of the envelopes of a multilinear
function. We provide preliminary computational experience on a variety
of global optimization problems. We compare the strength of various
commonly used relaxations for the multilinear expressions, discuss
generalizations to multilinear sets. | | | Title: | Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs | | Lead: | Binyuan Chen,PhD Students, University of Arizona, SIE Department, Tucson AZ 85721, United States of America, bychen@email.arizona.edu
| | Co-Author: | Simge Kucukyavuz,Ohio State University, Columbus OH 43202, United States of America, kucukyavuz.2@osu.edu
| | | Suvrajeet Sen,Professor, The Ohio State University, 1971 Neil Ave, Columbus OH 43210, United States of America, sen.22@osu.edu
| | Abstract: | We
give a finite disjunctive programming procedure to obtain the convex
hull of bounded general mixed-integer linear programs. We propose a
sequential disjunctive cutting plane algorithm that converges to an
integral optimal solution in finitely many iterations. We illustrate
the proposed algorithm on three well-known examples in the literature. | | |
|
Delete | | | 16:30 - 18:00 : Complementarity, Conality, and SDP - Algorithms and Applications |
| Chair: | Robert Vanderbei,Professor, Princeton University, Sherrerd Hall, Room 106, Princeton NJ 08544, United States of America, rvdb@princeton.EDU
| Title: | A Disjunctive Programming Approach to LPCC | | Lead: | Bin Yu,Graduate
student, Rensselaer Polytechnic Institute, CII5015 Rensselaer
Polytechnic Institute, 110 8th St., Troy NY 12180, United States of
America, yub@rpi.edu
| | Co-Author: | John Mitchell,Professor,
Rensselaer Polytechnic Institute, Department of Mathematical Sciences,
110 Eighth Street, Troy NY 12180, United States of America,
mitchj@rpi.edu
| | Abstract: | A
linear program with complementarity constraints (LPCC) can be modeled
as a disjunctive program. By imposing one pair of disjunctive
constraints at a time, we are able to use a cut generating LP to
generate a disjunctive cut for the LPCC problem. We present a branch
and cut algorithm to globally solve the LPCC problem. The algorithm is
able to characterize infeasible and unbounded LPCC problems as well as
solve problems with finite optimal value. | | | Title: | Optimization over the Doubly Non-Negative Cone | | Lead: | Akiko Yoshise,Professor, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Ibaraki, Japan, yoshise@sk.tsukuba.ac.jp
| | Co-Author: | Yasukaki Matsukawa,University of Tsukuba, Tsukuba, Ibaraki 305-8573, Ibaraki, Japan, matsuk50@sk.tsukuba.ac.jp
| | Abstract: | While
many studies on semidefinite relaxation for combinatorial optimization
problems force the solution matrix to be symmetric and positive
semidefinite, we often see that it is meant to be non-negative.
We call the set of such matrices the doubly non-negative cone.
Aiming to develop new algorithms for solving optimization problems over
the cone, we provide some basic properties of the doubly non-negative
cone focusing on barrier functions on its interior and its duality.
| | | Title: | Solving an Image Deconvolution Problem | | Lead: | Robert Vanderbei,Professor, Princeton University, Sherrerd Hall, Room 106, Princeton NJ 08544, United States of America, rvdb@princeton.EDU
| | Abstract: | A
recent paper by A. Leshem shows how high resolution imaging in radio
astronomy can be formulated as a block 2x2 semidefinite programming
problem. In this talk, I will describe the problem and show how it can
be solved efficiently as a convex optimization problem. | | | Title: | Interior-Point Methods for MPECs | | Lead: | Hande Benson,Assistant Professor, Drexel University, 3141 Chestnut St, Philadelphia PA 19104, United States of America, hvb22@drexel.edu
| | Co-Author: | Arun Sen,sen@post.harvard.edu
| | | David Shanno,RUTCOR, Rutgers University, New Brunswick, United States of America, shannod@comcast.net
| | Abstract: | Penalty
approaches for interior-point methods have been favored to handle the
unbounded multipliers when solving mathematical programs with
equilibrium constraints (MPECs). Even without this remedy,
interior-point methods are quite successful at solving many MPECs in
practice. In this talk, we will present a globally convergent
interior-point method which uses a penalty approach and analyze its
numerical performance on MPECs. Comparisons to non-penalty
interior-point methods will be provided. | | |
|
Delete | | | 16:30 - 18:00 : Matrix Rank Minimization: Theory and Algorithms |
| Chair: | Maryam Fazel,Assistant
professor, University of Washington, Campus Box 352500, Univ of
Washington, Seattle WA 98195, United States of America,
mfazel@u.washington.edu
| Title: | Matrix Completion from A Few Entries | | Lead: | Andrea Montanari,Professor, Standord University, Packard Bldg, Stanford CA 94025, United States of America, montanar@stanford.edu
| | Co-Author: | Raghunandan Keshavan,Stanford University, Stanford, United States of America, raghuram@stanford.edu
| | | Sewoong Oh,Stanford University, Stanford, United States of America, swoh@stanford.edu
| | Abstract: | We
consider the use of low-rank models in collaborative filtering (the
`Netflix problem'). Given M, a n x n `incoherent' matrix of rank r, a
random subset of its entries is observed. We describe an efficient
algorithm that reconstructs M from O(rn) entries with arbitrarily small
RMSE. If r = O(1), it reconstructs M exactly from O(n log n) entries.
The algorithm is robust with respect to noise. In the case of gaussian
noise, it appears to surpass approaches based on nuclear norm
relaxation. | | | Title: | Exact Matrix Completion via Convex Optimization | | Lead: | Emmanuel Candes,CalTech, emmanuel@acm.caltech.edu
| | Co-Author: | Terence Tao,University of California at Los Angeles, MC 1555, Los Angeles CA 90095, United States of America, tao@math.ucla.edu
| | Abstract: | We
observe a few entries from a matrix and ask whether we can complete the
matrix and recover the entries we have not seen. This is the famous
Netflix problem. We show that surprisingly one can recover low-rank
matrices exactly from what appear to be highly incomplete sets of
entries. Further, perfect recovery is possible by solving a
semidefinite program. Our methods are optimal and succeed as soon as
recovery is possible by any method whatsoever. | | | Title: | Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization | | Lead: | Shiqian Ma,Columbia University, 500 W. 120TH ST, Mudd Building, RM 313, New York NY 10027, United States of America, sm2756@columbia.edu
| | Co-Author: | Donald Goldfarb,Professor, Columbia University, New York, New York, United States of America, goldfarb@columbia.edu
| | Abstract: | We
consider in this talk the linearly constrained matrix rank minimization
problem. We propose fixed point and Bregman iterative algorithms for
solving the nuclear norm minimization problem, which is the tightest
convex relaxation of this problem. Our algorithm can recover 1000 by
1000 matrices of rank 50 with a relative error of 1e-5 in about 3
minutes sampling only 20 percent of the elements. We know of no other
method that achieves as good recoverability. | | | Title: | Results on Low-rank Matrix Recovery from Noisy Data | | Lead: | Maryam Fazel,Assistant
professor, University of Washington, Campus Box 352500, Univ of
Washington, Seattle WA 98195, United States of America,
mfazel@u.washington.edu
| | Abstract: | We
consider the problem of recovering a low-rank matrix from various
classes of limited and noisy observations. We show that minimizing the
nuclear norm of the matrix (i.e., the sum of its singular values)
subject to the observations provides not only a provably good
approximation of the unknown matrix, but also a way to estimate the
correct rank and the singular spaces of the matrix. | | |
|
Monday Oct 12
| Delete | | | 08:00 - 09:30 : Advanced Portfolio Theory and Practice |
| Chair: | John Mulvey,Professor, Princeton University, Sherrerd Hall, Princeton NJ 08540, United States of America, mulvey@princeton.edu
| Title: | Portfolio Theory versus Financial Engineering and Their Roles in Financial Crises | | Lead: | Harry Markowitz,harryhmm@aol.com
| | Abstract: | | | | Title: | Replicating Private Equity Returns with Exchange Traded Funds | | Lead: | John Mulvey,Professor, Princeton University, Sherrerd Hall, Princeton NJ 08540, United States of America, mulvey@princeton.edu
| | Abstract: | | | | Title: | Value-at-Risk vs. Conditional Value-at-Risk in Risk Management and Optimization | | Lead: | Stan Uryasev,University
of Florida, Dept. of Industrial and Systems Engineer, 303 Weil Hall,
P.O. Box 116595, Gainesville FL 32611-6595, United States of America,
uryasev@ufl.edu
| | Abstract: | From
the mathematical perspective, risk management is a
procedure for shaping a risk distribution. Two popular risk measures
are Value at-Risk (VaR) and Conditional Value-at-Risk (CVaR). This
paper presents our personal experience working with these key
percentile risk measures. We explain strong and weak features of these
risk measures. We discuss related case studies conducted with the
Portfolio Safeguard package.
| | | Title: | Managing a Fixed-income Portfolio | | Lead: | Roger Wets,Professor, University of California, Davis, EpiRisk Research, CA, United States of America, rjbwets@epirisk.com
| | Abstract: | As
stressed by Markowitz in the early 1950s and many others since,
investors can't ignore risk. This has led to widely implemented
mean-variance models. This lecture describes an alternative approach
relying on i) a more comprehensive description of uncertainty that
takes into account historical and market (term structures) information
and, ii) on an approximate assessment of the manager's risk aversion
whose parameters can be (easily)adjusted based on the(projected)
distribution of returns.
| | |
|
Delete | | | 08:00 - 09:30 : Optimization in Practice I - Algorithms |
| Co-Chair: | Robert Vanderbei,Professor, Princeton University, Sherrerd Hall, Room 106, Princeton NJ 08544, United States of America, rvdb@princeton.EDU
| Chair: | Ernest Forman,Dr.,
Department of Decision Science, School of Business, George Washington
University, Washington DC 20052, United States of America,
forman@gwu.edu
| | Bjarni Kristjansson,President,
Maximal Software, Inc., 2111 Wilson Boulevard, Suite 700, Arlington VA
22201, United States of America, bjarni@maximalsoftware.com
| Title: | Solving Practical Problems with Hybrid Optimization Approaches | | Lead: | Genetha Gray,gagray@sandia.gov
| | Co-Author: | Katie Fowler,Clarkson University, 8 Clarkson Avenue, Potsdam NY 13699, United States of America, kfowler@clarkson.edu
| | | Joshua Griffin,SAS Institute Inc, 100 SAS Campus Drive, Cary NC 27513, United States of America, joshua.griffin@sas.com
| | Abstract: | In
this talk, we will review the EAGLS (Evolutionary Algorithm Guiding
Local Search) software which allows for the hybridization of one or
more optimization methods. We will focus on the design characteristics
of EAGLS which make it particularly applicable for solving mixed
integer problems that arise in hydrological system design. | | | Title: | Determining an Optimal Portfolio of Projects: Project Portfolio Management | | Lead: | Ernest Forman,Dr.,
Department of Decision Science, School of Business, George Washington
University, Washington DC 20052, United States of America,
forman@gwu.edu
| | Co-Author: | Raj Kanungo,Associate
Professor, George Washington University, Department of Decision
Sciences, Washington DC 20052, United States of America, kanungo@gwu.edu
| | | William Taylor,Chief,
Operations Analysis, US Bureau of Citizenship and Immigration Services,
US Bureau of Citizenship and Immigration, Department of Homeland
Security, Washington DC, United States of America,
William.R.Taylor@dhs.gov
| | Abstract: | Determining
an optimal portfolio of projects involves two phases: prioritizing --
developing ratio scale measures of anticipated benefits with respect to
an organizations hierarchy of objectives, and determining a combination
of projects that maximizes the anticipated benefits subject to
dependencies and resource constraints. Three types of risk must also be
addressed: business risk, project risk, and portfolio risk. | | | Title: | Combinatorial Optimization Algorithms for Fault Diagnosis in Complex Systems | | Lead: | Krishna Pattipati,krishna@engr.uconn.edu
| | Abstract: | In
this talk, we will first discuss a unified methodology for intelligent
diagnostics that judiciously combines hybrid
model-based/data-driven/knowledge-based techniques that seamlessly
employs quantitative models, machine learning techniques and
graph-based dependency models to address real-time diagnosis, test
sequencing (NP-hard optimization problems), and remaining life
predictions (solution of partial differential equations) as well as the
associated maintenance optimization problems. | | |
|
Delete | | | 08:00 - 09:30 : Portfolio Optimization |
| Chair: | Victor DeMiguel,Associate Professor, London Business School, Regents Park, London NW14SA, United Kingdom, avmiguel@london.edu
| Title: | A Pathwise Algorithm for Covariance Selection | | Lead: | Alexandre d'Aspremont,Princeton
University, Dept of Operations Res & Fin Eng, Princeton University,
Princeton NJ 08544, United States of America, aspremon@princeton.edu
| | Co-Author: | VIjay Krishnamurthy,Princeton University, Sherrerd Hall, Princeton, United States of America, kvijay@nospamfrominforms.org
| | Abstract: | Covariance
selection seeks to estimate a covariance matrix by maximum likelihood
while restricting the number of nonzero inverse covariance matrix
coefficients. A single penalty parameter usually controls the tradeoff
between log likelihood and sparsity in the inverse matrix. We describe
an efficient algorithm for computing a full regularization path of
solutions to this problem.
| | | Title: | Efficient Estimation of Large Dynamic Multivariate Volatility Models for Portfolio Optimization | | Lead: | Francisco J. Nogales,Associate Professor, Universidad Carlos III de Madrid, Dept. of Statistics, Madrid, Spain, FcoJavier.Nogales@uc3m.es
| | Abstract: | In
large portfolio selection problems, the estimation of dynamic
multivariate volatility models (maximization of a nonlinear likelihood
function subject to a constraint ensuring the positiveness of all the
conditional covariance matrices) becomes unstable. This is mainly due
to the need of inverting all the conditional matrices at each
iteration. We propose new multivariate volatility specifications and
compare the resulting portfolio performance with that of several recent
proposals. | | | Title: | Exploiting Asset Return Predictability for Portfolio Selection | | Lead: | Victor DeMiguel,Associate Professor, London Business School, Regents Park, London NW14SA, United Kingdom, avmiguel@london.edu
| | Co-Author: | Francisco J. Nogales,Associate Professor, Universidad Carlos III de Madrid, Dept. of Statistics, Madrid, Spain, FcoJavier.Nogales@uc3m.es
| | Abstract: | There
is extensive evidence in the Finance literature about the
predictability of asset returns. We explore the use of parametric and
nonparametric statistical methods to exploit asset return
predictability for portfolio selection, and show that substantial
certainty equivalent gains can be achieved. | | |
|
Delete | | | 11:00 - 12:30 : Computational Stochastic Integer Programming |
| Chair: | David Morton,Professor,
The University of Texas at Austin, Graduate Program in Operations
Research, 1 University Station C2200, Austin TX 78712, United States of
America, morton@mail.utexas.edu
| Title: | Nuclear Medicine Patient and Resource Scheduling via Stochastic Integer Programming | | Lead: | Eduardo Perez,Graduate Student, Texas A & M University, 3131 TAMU, College Station TX, United States of America, eduardopr@neo.tamu.edu
| | Co-Author: | Cesar O. Malave,Professor, Texas A & M University, 3131 TAMU, College Station TX 77843, United States of America, malave@tamu.edu
| | | Lewis Ntaimo,Assistant Professor, Texas A&M University, 3131 TAMU, College Station TX 77843, United States of America, ntaimo@tamu.edu
| | Abstract: | Nuclear
medicine (NM) procedures use radioisotopes for diagnosis and treatment
of patients, involve multiple steps, and have to be performed under
strict time constraints and uncertainty in patient/radioisotope
arrivals. This makes the problem of NM patient service management very
challenging. We present stochastic integer programming models for NM
patient/resource scheduling within a stochastic online optimization
framework. A computational study based on an actual NM clinic will be
presented. | | | Title: | Parallelization of Progressive Hedging Revisited: Asynchronous Convergence and Scenario Bundling | | Lead: | David Woodruff,Professor,
University of California Davis, UC Davis, Davis, CA 95616, Davis CA,
United States of America, dlwoodruff@ucdavis.edu
| | Co-Author: | Jean-Paul Watson,Principal
Member of Technical Staff, Sandia National Laboratories, P.O. Box 5800,
MS 1318, Albuquerque NM 87185-1318, United States of America,
jpwatson@sandia.gov
| | Abstract: | Although Progressive Hedging is naturally parallelizable, a number of unexplored issues arise for
efficient implementation. In particular, asynchronous sub-problem solves facilitate improved efficiency,
but may adversely impact algorithm convergence. Similarly, intelligent bundling of scenarios may accelerate
local convergence, but degrade global convergence. We explore the practical implementation of these techniques,
and discuss computational results on various test problems.
| | | Title: | Prioritization via Stochastic Optimization | | Lead: | Ali Koc,The University of Texas at Austin, alikoc@mail.utexas.edu
| | Co-Author: | David Morton,Professor,
The University of Texas at Austin, Graduate Program in Operations
Research, 1 University Station C2200, Austin TX 78712, United States of
America, morton@mail.utexas.edu
| | | Elmira Popova,The
University of Texas at Austin, 1 University Station, C2200, Austin TX
78712, United States of America, elmira@mail.utexas.edu
| | Abstract: | The
operations research literature handles activity selection problems by
forming an optimal portfolio of activities, as opposed to a common
approach in industry which forms a prioritized list. We develop a novel
prioritization approach incorporating both views. We illustrate our
approach on stochastic k-median and capital budgeting models. We
formulate two-stage and multi-stage stochastic integer programs and
develop valid inequalities. We use parallel branch-cut-price to improve
solution time. | | |
|
Delete | | | 13:30 - 15:00 : New Trends in Optimization |
| Chair: | Angelia Nedich,Assistant
Professor, University of Illinois at Urbana-Champaign, 117
Transportation Building, 104 South Mathews Avenue, Urbana IL 61801,
United States of America, angelia@illinois.edu
| Title: | Testing the Nullspace Property using Semidefinite Programming | | Lead: | Alexandre d'Aspremont,Princeton
University, Dept of Operations Res & Fin Eng, Princeton University,
Princeton NJ 08544, United States of America, aspremon@princeton.edu
| | Co-Author: | Laurent El Ghaoui,U.C. Berkeley, Somewhere, Berkeley, United States of America, elghaoui@nospamforhim.com
| | Abstract: | Recent
results in compressed sensing show that, under certain conditions, the
sparsest solution to an underdetermined set of linear equations can be
recovered by solving a linear program. Given a matrix $A$, we use
semidefinite relaxation techniques to test the nullspace property on
$A$ and show on some numerical examples that these relaxation bounds
can prove perfect recovery of sparse solutions with relatively high
cardinality.
| | | Title: | Sparse Solutions of Standard Quadratic Programmimng Problems with Random Matrices | | Lead: | Jiming Peng,Assistant
Professor, University of Illinois at Urbana-Champaign, 117
Transportation Building, 104 S. Mathews Ave., Urbana IL 61801, United
States of America, pengj@illinois.edu
| | Abstract: | In
this talk, we investigate the properties of the solutions of the
so-called standard quadratic programming problems (StQP), which has
been proved to be NP-hard. Motivated by the recent results in
compressed sensing, we focus on the scenarios where the associated
matrix is random. We show that if all the elements of the underlying
matrix follow i.i.d., then the corresponding StQP has a very sparse
solution with a high probability. | | | Title: | Online Learning and Interior Point Algorithms for MDPs with Expected Budget Constraints
| | Lead: | Constantine Caramanis,The University of Texas at Austin, Austin TX, cmcaram@ece.utexas.edu
| | Co-Author: | Nedialko Dimitrov,The
University of Texas at Austin, Department of Mechanical Engineering, 1
University Station C2200, Austin TX 78712, United States of America,
ned.dimitrov@gmail.com
| | | David Morton,Professor,
The University of Texas at Austin, Graduate Program in Operations
Research, 1 University Station C2200, Austin TX 78712, United States of
America, morton@mail.utexas.edu
| | Abstract: | An
MDP with n states can be solved using the value iteration algorithm in
O(n^2) time, as opposed to the Omega(n^3) time required if one uses a
linear program. Expected budget constraints on the MDP policy can be
easily captured in a linear program formulation, but break the basic
value iteration algorithm. We show two new algorithms for solving MDPs
with k budget constraints giving the exact solution in O(poly(k) n^2)
time or an approximately feasible solution in O(log(k) n^2) time.
| | | Title: | Distributed Asynchronous Stochastic Optimization Method | | Lead: | Angelia Nedich,Assistant
Professor, University of Illinois at Urbana-Champaign, 117
Transportation Building, 104 South Mathews Avenue, Urbana IL 61801,
United States of America, angelia@illinois.edu
| | Abstract: | We
consider a distributed method over a network for optimizing a convex
objective function, which is known to all agents in the network. At any
given time, one agent updates and passes its estimate to one of its
neighbors according to a Markov chain distribution. We consider a
gradient-based scheme, and establish some convergence properties and
error bounds on the performance. | | |
|
Delete | | | 13:30 - 15:00 : The Rise and Fall and Rise Again of Interior-Point Methods |
| Chair: | Margaret Wright,Courant Institute of Mathematical Sciences, 251 Mercer Street, New York 10012, United States of America, mhw@cs.nyu.edu
| Title: | Then and Now: The Renaissance of Interior-Point Methods for Nonlinear Programming Part 1 | | Lead: | Margaret Wright,Courant Institute of Mathematical Sciences, 251 Mercer Street, New York 10012, United States of America, mhw@cs.nyu.edu
| | Abstract: | The
1984 "interior-point revolution" in optimization could equally well be
called an "interior-point renaissance" because of its interconnected
combination of old and new ideas. The two speakers will address several
themes, including: the pre-1984 rise and fall of interior-point
methods; old ideas that have been revived and extended; and genuinely
new ideas related to computational complexity, ties with linear
algebra, and approaches for large-scale problems. | | | Title: | Then and Now: The Renaissance of Interior-Point Methods for Nonlinear Programming (Part 2) | | Lead: | Philip Gill,Professor,
University of California, San Diego, 9500 Gilman Drive, # 0112, La
Jolla CA 92093-0112, United States of America, pgill@ucsd.edu
| | Abstract: | The
1984 "interior-point revolution" in optimization could equally well be
called an "interior-point renaissance" because of its interconnected
combination of old and new ideas. The two speakers will address several
themes, including: the pre-1984 rise and fall of interior-point
methods; old ideas that have been revived and extended; and genuinely
new ideas related to computational complexity, ties with linear
algebra, and approaches for large-scale problems. | | | Title: | Interior Point Methods for Very Large Scale Optimization 25 Years Later | | Lead: | Jacek Gondzio,Prof, Edinburgh University, School of Mathematics, Edinburgh EH9 2EA, United Kingdom, J.Gondzio@ed.ac.uk
| | Abstract: | This talk will focus on remaining challenges faced by interior
point methods for very large scale optimization. In particular,
the issues of iterative methods and a choice of suitable
preconditioners to solve reduced Newton systems arising
in optimization with interior point methods will be addressed. | | |
|
Tuesday Oct 13
| Delete | | | 08:00 - 09:30 : Methods for Large-Scale Nonlinear Optimization |
| Chair: | Philip Gill,Professor,
University of California, San Diego, 9500 Gilman Drive, # 0112, La
Jolla CA 92093-0112, United States of America, pgill@ucsd.edu
| Title: | Solution of a Stochastic Model for Allocation of On-line Advertising Inventory | | Lead: | John Tomlin,Yahoo! Labs, 701 First Avenue, Sunnyvale CA 94089, United States of America, tomlin@yahoo-inc.com
| | Co-Author: | Vijay Bharadwaj,Yahoo! Inc., 701 First Avenue, Sunnyvale CA 94089, United States of America, vbharadw@yahoo-inc.com
| | | MIchael Saunders,MSE Department, Stanford University, Stanford CA 94305, United States of America, saunders@stanford.edu
| | Abstract: | We describe the stochastic extension of a transportation
model with separable convex objective for optimal allocation of online
advertising inventory for guaranteed delivery. Using the approach
pioneered by Beale and Dantzig, we arrive at a stochastic model that
is also convex and separable. We apply a C++ version of the
primal-dual interior solver PDCO.
| | | Title: | An Interior-point Trust-funnel Algorithm for Large-scale Nonconvex Optimization | | Lead: | Daniel Robinson,Oxford University, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom, daniel.p.robinson@gmail.com
| | Co-Author: | Nick Gould,Professor, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire OX11 0QX, United Kingdom, nick.gould@stfc.ac.uk
| | | Philippe Toint,FUND-P University of Namur, 61 Rue de Bruxelles, B-5000, Namur, Belgium, philippe.toint@fundp.ac.be
| | Abstract: | We discuss an interior-point trust-funnel algorithm for large-scale nonconvex optimization. Global
convergence of our method is ensured by trust-region methodology
combined with the so-called ``funnel''. The prominent features of
our algorithm are that each subproblem may be solved
approximately and that inexact SQP steps may be computed when
deemed advantageous during the course of solving each barrier subproblem. | | | Title: | SQP Methods for Nonlinear Optimization | | Lead: | Philip Gill,Professor,
University of California, San Diego, 9500 Gilman Drive, # 0112, La
Jolla CA 92093-0112, United States of America, pgill@ucsd.edu
| | Co-Author: | Elizabeth Wong,University
of California, San Diego, 9500 Gilman Drive, # 0112, La Jolla CA
92093-0112, United States of America, elwong@ucsd.edu
| | Abstract: | We
consider the formulation and analysis of sequential quadratic
programming (SQP) methods for large-scale nonlinearly constrained
optimization that may be ``hot started'' from a good approximate
solution. In this context we focus on SQP methods that are best able to
use ``black-box'' linear algebra software. Such methods provide an
effective way of exploiting recent advances in linear algebra software
for multicore and GPU-based computer architectures
| | |
|
Delete | | | 08:00 - 09:30 : IEEE Transactions on Automation Science & Engineering Sponsored Session |
| Co-Chair: | Yu Ding,Associate
Professor, Texas A&M University, 3131 MS, College Station TX 77843,
United States of America, yuding@iemail.tamu.edu
| Chair: | N. Viswanadham,N_Viswanadham@isb.edu
| Title: | Port-of-Entry Inspection: Sensor Deployment Policy Optimization | | Lead: | Elsayed Elsayed,Professor,
Rutgers University, Industrial and Systems Engineering, Piscataway NJ
08854, United States of America, elsayed@rci.rutgers.edu
| | Co-Author: | Minge Xie,Associate
professor, Rutgers University, Department of Statistics, Piscataway NJ
08854, United States of America, mxie@stat.rutgers.edu
| | | Christina Young,PhD
Candidate, Rutgers University, Industrial and Systems Engineering Dept,
Piscataway NJ 08854, United States of America, cms168@rci.rutgers.edu
| | | Hao Zhang,Rutgers University, Industrial and Systems Eng., Piscataway NJ 08854, United States of America, haoz88@gmail.com
| | | Yada Zhu,Graduate
Student, Rutgers University, Industrial and Systems Engineering,
Piscataway NJ 08854, United States of America, yadazhu@eden.rutgers.edu
| | Abstract: | At
the port-of-entry containers are inspected through a sequence of
stations to detect illegal cargo. The inspection policy, which includes
the sequence in which sensors are applied and the threshold levels used
at the inspection stations, affects the probability of misclassifying a
container as well as the cost and time spent in inspection. We will
present our work in the optimization of such inspection systems, as
well as recent investigation to reduce the effect of measurement error. | | | Title: | Sensor Selection in Arbitrary Dimensions | | Lead: | Malik Magdon-Ismail,Associate Professor, Rensselaer Polytechnic Institute, magdon@cs.rpi.edu
| | Co-Author: | Volkan Isler,University of Minnesota, United States of America, isler@cs.umn.edu
| | Abstract: | We
address the sensor selection problem which arises in tracking and
localization applications. In sensor selection, the goal is to select a
small number of sensors whose measurements provide a good estimate of a
target’s state. We focus on the bounded uncertainty sensing model where
the target is a point in the d dimensional Euclidean space, and show
that, on the plane, four sensors are sufficient to obtain an estimate
whose area is at most twice the area of the best possible estimate. | | | Title: | Identification of Influential Process Variables for Surface Quality Control in Hot Rolling | | Lead: | Shiyu Zhou,University
of Wisconsin-Madison, Department of Industrial and Systems Engineering,
1513 University Avenue, Madison WI 53706-1572, United States of
America, szhou@engr.wisc.edu
| | Co-Author: | Tzyy-Shuh Chang,OG Technologies, 4300 Varsity Drive, Ann Arbor, United States of America, chang@ogtechnologies.com
| | | Howard Huang,OG technologies, 4300 Varsity Drive, Ann Arbor, United States of America, huang@ogtechnologies.com
| | | Nong Jin,University of Wisconsin - Madison, 1513 University Ave., Madison, United States of America, nong.jin@capitalone.com
| | Abstract: | Surface
defects have been a long-term troubling issue in hot rolling processes.
In this paper, functional data analysis and rigorous statistical
testing are integrated to identify the process variables that
significantly influence the surface quality of the finished products.
The results can provide guidelines for root cause identification and
surface quality improvement in hot rolling processes. | | |
|
Delete | | | 08:00 - 09:30 : Joint Session ICS/DM Optimization in Data Mining/Machine Learning |
| Chair: | Paul Brooks,Virginia Commonwealth University, PO Box 843083, Richmond VA 23229, United States of America, jpbrooks@vcu.edu
| Title: | Solving the Sparse PCA SDP Relaxation | | Lead: | David Phillips,Assistant
Professor, College of William & Mary, Math Department, Williamsburg
VA 23185, United States of America, djphil@wm.edu
| | Co-Author: | Garud Iyengar,Associate Professor, Columbia University, IEOR Department, New York NY 10027, United States of America, garud@ieor.columbia.edu
| | | Cliff Stein,Professor, Columbia University, IEOR Department, New York NY 10027, United States of America, cliff@ieor.columbia.edu
| | Abstract: | In
this presentation, we present an algorithm to solve the Sparse PCA SDP
relaxation. Our solution algorithm solves a Lagrangian saddle point
problem via a prox method of Nesterov's. Some key differences in our
approach from previous algorithms is our use of a quadratic prox
function and that we return feasible solutions to the SDP relaxation,
where the former leads to a better run theoretical bound. Experimental
results are presented. | | | Title: | Relaxing Support Vectors with Linear and Quadratic Programming Models | | Lead: | Onur Seref,Assistant Professor, Virginia Tech, 1007 Pamplin Hall (0235), Blacksburg VA 24061, United States of America, seref@vt.edu
| | Abstract: | In
this talk, we introduce linear and quadratic programming models to
relax vectors that are usually misclassified by maximal margin
classifiers using a restricted amount of free (unpenalized) total
slack. We introduce kernelized versions and emphasize important
properties of these models. We also introduce a simple 2-phase method
based on these models for multiple instance classification and present
competitive computational results on public benchmark datasets and
neurological data. | | | Title: | From Pictures to 3D: A Global Optimization Approach | | Lead: | Manmohan Chandraker,University of California, San Diego, La Jolla, United States of America, mkchandraker@cs.ucsd.edu
| | Co-Author: | Sameer Agarwal,University of Washington, Seattle, Seattle, United States of America, sagarwal@cs.washington.edu
| | | Serge Belongie,University of California, San Diego, La Jolla, United States of America, sjb@cs.ucsd.edu
| | | David Kriegman,University of California, San Diego, La Jolla 92093, United States of America, kriegman@cs.ucsd.edu
| | Abstract: | We
present practical algorithms for achieving globally optimal solutions
for 3D scene reconstruction from 2D images. We pose the non-convex
problem as a fractional program and construct efficient convex
envelopes to perform minimization in a branch and bound paradigm. A
unified framework is developed for minimizing the standard L2-norm as
well as the robust L1-norm. We demonstrate that exploiting domain
knowledge can alleviate branch and bound's worst case exponential
complexity in practice. | | | Title: | Locally Linear Support Vector Machines | | Lead: | Paul Brooks,Virginia Commonwealth University, PO Box 843083, Richmond VA 23229, United States of America, jpbrooks@vcu.edu
| | Co-Author: | Vojislav Kecman,VCU, PO Box 843019, Richmond VA 23284, United States of America, vkecman@vcu.edu
| | Abstract: | In
this talk we present a new method for combining the k-nearest neighbors
(KNN) and support vector machines (SVM) to produce a classifier that
reflects local patterns in data. The Locally Linear SVM (LLSVM) is able
to maximize margin and minimize error in the input feature space for
points in the neighborhood of a query and derive globally complex
separating surfaces. Theoretical evidence of the superior stability of
LLSVM over global (traditional) SVM is given. | | |
|
Delete | | | 11:00 - 12:30 : Optimization in Practice IV - Software |
| Co-Chair: | Bjarni Kristjansson,President,
Maximal Software, Inc., 2111 Wilson Boulevard, Suite 700, Arlington VA
22201, United States of America, bjarni@maximalsoftware.com
| Chair: | Rob Suggs,CEO, Vanguard Software Corporation, 1100 Crescent Green, Cary NC 27518, United States of America, rob.suggs@vanguardsw.com
| Title: | Optimization in Strategic Business Planning | | Lead: | Rob Suggs,CEO, Vanguard Software Corporation, 1100 Crescent Green, Cary NC 27518, United States of America, rob.suggs@vanguardsw.com
| | Abstract: | Applying
optimization techniques to strategic business planning can provide
benefits that are potentially far greater than those realized by
optimizing routine business operations. Quite simply, doing the right
thing is far more important than doing the wrong thing well. We discuss
the lessons learned in Vanguard's development of a forecasting and
stochastic optimization solution that Novartis Vaccines &
Diagnostics uses to optimize its drug investment activities. | | | Title: | Efficient Optimization with Portfolio Safeguard Software | | Lead: | Stan Uryasev,University
of Florida, Dept. of Industrial and Systems Engineer, 303 Weil Hall,
P.O. Box 116595, Gainesville FL 32611-6595, United States of America,
uryasev@ufl.edu
| | Abstract: | We
will present several case studies mostly in financial optimization area
conducted using Portfolio Safeguard optimization software. Case studies
will cover the following topics: portfolio optimization and portfolio
hedging with downside risk measures such as VaR, CVaR, Drawdown, and
others. | | | Title: | Valid Inequalities for an Integer Programming Model for Software Projects with Soft Deadlines | | Lead: | Ishwar Murthy,Professor, Indian Institute of Management, Bannerghatta Road, Bangalore 560076, India, ishwar@IIMB.ERNET.IN
| | Co-Author: | Kaushik Dutta,Associate
Professor, Florida International University, Decision Sciences &
Information Systems, College of Business Administration, Miami FL
33199, United States of America, Kaushik.Dutta@fiu.edu
| | | Sridhar Narasimhan,Professor,
Georgia Institute of Technology, College of Management, 800 West
Peachtree St, NW, Atlanta GA 30308, United States of America,
Sri.Narasimhan@mgt.gatech.edu
| | Abstract: | We
develop an integer programming model that enables software development
companies manage software engineers (in-house and vendors) at their
disposal to complete their projects with minimal violation of the
project deadlines. The manpower requirement as well as the skill sets
required for each project in each time period is known. The above
NP-Hard problem is modeled as a multi-commodity path problem on an
acyclic graph, with side constraints. | | | Title: | OptForce™ Strategic Workforce Planning Technology: Combining Simulation and Optimization | | Lead: | Jay April,Chief
Development Officer, OptTek Systems, Inc., 1919 Seventh Street, Boulder
CO 80302, United States of America, april@opttek.com
| | Co-Author: | Marco Better,Director
of Custom Solutions, OptTek Systems, 1919 Seventh Street, Boulder CO
80302, United States of America, better@opttek.com
| | | Fred Glover,CTO, OptTek Systems, 1919 Seventh Street, Boulder CO 80302, United States of America, glover@opttek.com
| | | James Kelly,CEO, OptTek Systems, 1919 Seventh Street, Boulder CO 80302, United States of America, kelly@opttek.com
| | Abstract: | This
presentation describes simulation optimization software technology
being developed under a National Science Foundation SBIR contract to be
used to enhance strategic workforce planning and management. The
software combines two innovative methods drawn from the field of
operations research: agent-based simulation and metaheuristic
optimization. The software, which is called OptForce™, is used to
evaluate decisions for creating, modifying, and eliminating workforce
policies and programs. | | |
|
Delete | | | 11:00 - 12:30 : Modeling and Optimization in Health Care |
| Chair: | Todd Easton,Associate Professor, Kansas State University, 2037 Durland Hall, Manhattan KS 66506, United States of America, teaston@ksu.edu
| Title: | A System Approach for Uncertainty Modeling in Clinical Laboratory Measurements | | Lead: | Varun Ramamohan,Graduate
Student (PhD), Department of Industrial Engineering, Purdue University,
315 North Grant Street, West Lafayette IN 47907, United States of
America, vramamoh@purdue.edu
| | Co-Author: | Jim Abbott,Manager,
Clinical Support Group, Roche Diagnsotics Corporation, 9115 Hague Road,
PO Box 50457, Indianapolis IN 46250-0457, United States of America,
jim.abbott@roche.com
| | | Vishal Chandrasekar,Graduate
Student (MS), Department of Industrial Engineering, Purdue University,
315 North Grant Street, West Lafayette IN 47907, United States of
America, vchandra@purdue.edu
| | | George Klee,Professor
of Laboratory Medicine & Pathology, Mayo Clinic College of
Medicine, 200 First Street SW, Rochester MN 55905, United States of
America, klee.george@mayo.edu
| | | Yuehwern Yih,Professor, Purdue University, 315 N. Grant Street, West Lafayette, United States of America, yih@purdue.edu
| | Abstract: | Systematic
errors in laboratory measurements have significant impact on clinical
decisions, patient safety and medical costs. A system approach towards
quality control of clinical laboratory measurements is described in
this paper. We present a calibration model that identifies the sources
of systematic error and then systematically analyzes the propagation of
these errors throughout the process. Monte Carlo simulation is used to
derive the general uncertainty measure for this bias. | | | Title: | Modeling the Treatment-prevention Tradeoff | | Lead: | George Miller,Institute
Fellow, Altarum Institute, 3520 Green Court, Suite 300, Ann Arbor MI
48105, United States of America, george.miller@altarum.org
| | Co-Author: | Matt Daly,Senior
Analyst, Altarum Institute, 3520 Green Court, Suite 300, Ann Arbor MI
48105, United States of America, matt.daly@altarum.org
| | Abstract: | It
is frequently claimed "with little quantitative evidence" that current
health care expenditures inappropriately emphasize treatment over
prevention. We are investigating this assertion using a dynamic model
of the impacts of alternative investments in treatment and prevention,
and in research to develop new treatment and prevention interventions,
on effectiveness (measured in quality adjusted life years). We describe
the structure of the model and emerging results from its application. | | | Title: | Radiation Quality Assurance with DICOM Information | | Lead: | Shanshan Wang,PhD Student, Arizona State University, School of CIDSE, Tempe AZ 85281, wshanshan@asu.edu
| | Co-Author: | Steve Langer,Associate Professor of Radiologic Physics, Radiology, Mayo Clinic, Arizona, AZ,
| | | Richard L. Morin,Brooks-Hollern Professor, Professor of Radiologic Physics, Radiology, Mayo Clinic, Rochester, AZ,
| | | William Pavlicek,Associate Professor of Radiologic Physics, Mayo Clinic, Radiology, AZ,
| | | Mary B. Peter,Physicist - Diagnostic Imaging, Radiology, Mayo Clinic, Rochester, AZ,
| | | Catherine C. Roberts,Associate Professor of Radiology, Radiology, Mayo Clinic, Arizona, AZ,
| | | Beth A. Schueler,Associate Professor of Radioligy, Radiology, Mayo Clinic, Rochester, AZ,
| | | Teresa Wu,Associate Professor, Arizona State University, Tempe AZ 85281, United States of America, teresa.wu@asu.edu
| | | Muhong Zhang,Asst
Professor, Arizona State University, Arizona State University,
Department of Industrial Engineering, Tempe 85287, United States of
America, Muhong.Zhang@asu.edu
| | Abstract: | The
oversight and monitoring of radiation dose use are required in federal
and state statutes. Digital Imaging and Communications in Medicine
(DICOM) standards is a widely adopted standard in radiation imaging
processing. In this study, we build an information system to capture
the information in DICOM compliant radiation images and explore their
use in routine quality assurance activities. The system consists of a
knowledge base of known devices (i.e. modalities), a patient episode
dose tracking database and a set of web-based reporting tools. The
implementation potentially provides quantitative data hints to reduce
radiation exposure and automates the radiation regulatory compliance
process. | | | Title: | The When Diet : Mathematically Optimizing Eating and Exercise for Weight Loss | | Lead: | Todd Easton,Associate Professor, Kansas State University, 2037 Durland Hall, Manhattan KS 66506, United States of America, teaston@ksu.edu
| | Abstract: | Over
the past five years I have studied the dieting problem and recently
published The When Diet: Mathematically Optimizing Eating and Exercise
for Weight Loss. This talk presents the major developments contained in
this book, including a mathematical proof of The When Diet, the
stochastic properties of hunger, lean manufacturing and how to minimize
the misery incurred by being on a diet while maximizing the amount of
weight lost.
| | |
|
Delete | | | 11:00 - 12:30 : Stochastic Optimization III |
| Chair: | Rahul Nair,Grad
Research Assistant, University of Maryland, 1173 Glenn Martin Hall,
College Park MD 20742, United States of America, rahul@umd.edu
| Title: | Definition of Maintenance Policies Applying Stochastic Optimization | | Lead: | Carlos Osorio-Ramirez,Politecnico Grancolombiano, Calle 57 3 00 Este Fac. Ingenieria, Bogota, Colombia, caosorio@poligran.edu.co
| | Co-Author: | Javier Nieto,DecisionWare, Cra 7 88 16 Of 202, Bogota, Colombia, javier.nieto@decisionware-ltd.com
| | | Jesus Velasquez,DecisionWare, Cra 7 88 16 Of 202, Bogota, Colombia, jesus.velasquez@decisionware-ltd.com
| | Abstract: | This
paper presents a non-anticipative stochastic optimization model in
order to determine the most common maintenance decisions, according to
a set of possible scenarios with some feasible sequences of failures. | | | Title: | Computational Experience of Solving Two-stage Stochastic Linear Programming Problems | | Lead: | Viktar Zviarovich,PhD Student, CARISMA, Brunel University, Kingston Lane, Uxbridge UB8 3PH, United Kingdom, viktar.zviarovich@brunel.ac.uk
| | Co-Author: | Francis Ellison,CARISMA, Brunel University, Kingston Lane, Uxbridge UB8 3PH, United Kingdom, francis.ellison@brunel.ac.uk
| | | Csaba Fabian,Institute of Informatics, Kecskemet College, 10 Izsaki ut, Kecskemet, Hungary, fabian.csaba@gamf.kefo.hu
| | | Gautam Mitra,CARISMA, Brunel University, West London, United Kingdom, gautam.mitra@brunel.ac.uk
| | Abstract: | We
present a computational study of two-stage SP solution algorithms for a
range of benchmark problems. We consider application of (1) Simplex
method and (2) IPM to solve deterministic equivalent problems, (3)
Benders decomposition, (4) stochastic decomposition and (5) three
regularisation methods. The first method is an experimental heuristic
regularisation. The last two are based on the level decomposition by
Fabian and Szoke. The scale-up properties and the performance profiles
are presented. | | | Title: | A Stochastic Inventory Model for Critical Spare Parts used for Maintenance of Construction Machines | | Lead: | Nihat Kasap,Assistant Professor, Sabanci University, Faculty of Management, Istanbul 34956, Turkey, nihatk@sabanciuniv.edu
| | Co-Author: | Ilker Bicer,Commandership
of Gendarmerie Military Engineering Corps, J. Istihkam Insaat Grup Kom.
Guvercinlik, Ankara, Turkey, ibicer73@gmail.com
| | Abstract: | We
develop a stochastic inventory model for critical spare parts used for
the maintenance of heavy construction machines. Proposed model is a
nonlinear integer optimization problem with average service level and
replenishment frequency constraints. The aim of the model is to find
out reorder points and stocking levels of critical spare parts that
minimize the inventory costs. We propose heuristic that contains
modified ABC Analysis and can be implemented with the spreadsheet
applications easily. | | | Title: | Progressive Hedging Applied to Stochastic Forestry Planning Problem | | Lead: | Fernando Badilla Veliz,Master
in OR thesist, Universidad de Chile, Beauchef 850, Santiago, Manuel de
Salas 35, depto. 151, Ñuñoa, Santiago, Chile, fbadilla@ing.uchile.cl
| | Co-Author: | Andres Weintraub,Professor, University of Chile, Beauchef 850, Santiago, Santiago, Chile, aweintra@dii.uchile.cl
| | | Roger Wets,Professor, University of California Davis, One Shields Avenue, Davis CA 95616, United States of America, rjbwets@ucdavis.edu
| | | David Woodruff,Professor,
University of California Davis, UC Davis, Davis, CA 95616, Davis CA,
United States of America, dlwoodruff@ucdavis.edu
| | Abstract: | The
problem consist in planning the optimal harvest, deciding when and
which lots to harvest, roads to build (binary decisions) and the wood
flow through these roads; under different probabilistic price,
demand and yield scenarios. We present an approach to solve this
integer stochastic problem which handles the non anticipativity
constraints based on the heuristic progressive hedging, decomposing the
problem so that it's not limited by the number of scenarios considered. | | | Title: | A Recursive Decomposition Algorithm for Generating p-Efficient Points | | Lead: | Rahul Nair,Grad
Research Assistant, University of Maryland, 1173 Glenn Martin Hall,
College Park MD 20742, United States of America, rahul@umd.edu
| | Co-Author: | Elise Miller-Hooks,Associate
Professor, University of Maryland, 1173 Glenn Martin Hall, College Park
MD 20742, United States of America, elisemh@umd.edu
| | Abstract: | p-efficient
points are employed in solving programs with joint chance constraints
where the random vector is discrete. Generating these points is
problematic when the number of dimensions or domain of the random
vector is large. A new recursive decomposition algorithm is proposed
that restricts the search to sub-domains that contain the p-frontier
thereby reducing the computation and memory requirements. | | |
|
Delete | | | 11:00 - 12:30 : Applications of SDP to EDM and other Polynomial Optimization Problems |
| Chair: | Henry Wolkowicz,University of Waterloo, Dept of Comb and Opt, Waterloo ON N2L 3G1, Canada, hwolkowi@uwaterloo.ca
| Title: | Universal Rigidity: Towards Accurate and Efficient Localization of Wireless Networks | | Lead: | Yinyu Ye,Professor,
Stanford University, 316 Terman Engineering Building, Stanford CA
94305, United States of America, yinyu-ye@stanford.edu
| | Co-Author: | Anthony Man-Cho So,The Chinese Univ of Hong Kong, Department of SE&EM, Shatin NT, Hong Kong - PRC, manchoso@se.cuhk.edu.hk
| | | Zhisu Zhu,Stanford University, 102 Hoskins Ct, Apt 419, Stanford CA 94305, United States of America, zhuzhisu@stanford.edu
| | Abstract: | We
propose a notion of universal rigidity that captures a large class of
wireless networks and is much more relevant to the efficient
solvability of network localization problems. We give various
constructions of universally rigid instances. We also apply our results
to design a novel edge sparsification scheme that can reduce the size
of the input network while provably preserving its original
localization properties. | | | Title: | Exploiting Sparsity in SDP Relaxation for Sensor Network Localization | | Lead: | Hayato Waki,Dr., The University of Electro-Communications, Chofugaoka, Chofu-Shi, Tokyo 182-8585, Japan, hayato.waki@jsb.cs.uec.ac.jp
| | Co-Author: | Sunyoung Kim,Professor, Ewha W. University, 11-1 DaHyun-Dong,, SuhDaeMoon-Gu, Seoul 120-750, Korea, Republic of, skim@ewha.ac.kr
| | | Masakazu Kojima,Professor, Tokyo Institute of Technology, 2-12-1-W8-29, Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan, kojima@is.titech.ac.jp
| | Abstract: | We
present a sparse variant of the Biswas-Ye SDP relaxation for sensor
network localization problems. We compare numerically the Biswas-Ye SDP
relaxation, its sparse variant, and the edge-based SDP relaxation by
Wang et al. to confirm the effectiveness of the proposed techniques for
exploiting sparsity in SDP relaxation for sensor network localization
problems. The sparse variant of the Biswas-Ye SDP relaxation
outperforms all other SDP relaxations in speed. | | | Title: | On SDP and ESDP Relaxations for Sensor Network Localization | | Lead: | Paul Tseng,Dept of Mathematics, University of Washington, Seattle, United States of America, tseng@math.washington.edu
| | Co-Author: | Ting Kei Pong,Ph.D.
student, University of Washington, Box 354350, Math, Univ. Washington,
Seattle WA 98195-4350, United States of America,
tkpong@math.washington.edu
| | Abstract: | We
study SDP and ESDP relaxations for ad hoc wireless sensor network
localization. In particular, we propose a noise-aware version whose
solution set is more robust in the presence of noisy distance
measurements. We also propose an efficient distributed method to find
an interior solution. | | | Title: | Explicit Sensor Network Localization Using Semidefinite Programming and Clique Reductions | | Lead: | Henry Wolkowicz,University of Waterloo, Dept of Comb and Opt, Waterloo ON N2L 3G1, Canada, hwolkowi@uwaterloo.ca
| | Co-Author: | Nathan Krislock,University of Waterloo, Dept. Comb. & Opt., Faculty of Mathematics, Waterloo ON N2L3G1, Canada, ngbkrisl@uwaterloo.ca
| | Abstract: | The
sensor network localization, SNL, problem consists of locating the
positions of sensors, given only the distances between sensors that
are within radio range and the positions of some fixed sensors (called
anchors). By finding explicit representations of the faces of the SDP
cone corresponding to unions of cliques of the SNL problem, we derive a
preprocessing technique that solves the SNL problem, with exact data,
by explicitly solving the corresponding SDP problem.
| | |
|
Delete | | | 13:30 - 15:00 : Algorithms and Applications of Polynomial Optimization and Robust Optimization |
| Chair: | X. Andy Sun,Doctoral
Candidate, Operations Research Center, MIT, 77 Massachusetts Ave.,
Cambridge MA 02139, United States of America, sunx@MIT.EDU
| Title: | Efficient First-Order Methods for Polynomial Optimization | | Lead: | X. Andy Sun,Doctoral
Candidate, Operations Research Center, MIT, 77 Massachusetts Ave.,
Cambridge MA 02139, United States of America, sunx@MIT.EDU
| | Co-Author: | Dimitris Bertsimas,Boeing
Professor of Operations Research, Massachusetts Institute of
Technology, 77 Massachusetts Avenue, Bldg. E40-149, Cambridge MA 02139,
United States of America, dbertsim@mit.edu
| | | Robert Freund,Professor,
MIT, Sloan School of Mgmt., E52-476, 50 Memorial Drive, Cambridge MA
02142, United States of America, rfreund@mit.edu
| | Abstract: | We
apply efficient first-order methods to polynomial optimization
problems (POPs), which are generally difficult to solve. By exploiting
special structure of the SDP representation of the POP, we demonstrate
that first-order methods have the promise to improve the computational
solvability of general POPs. We also explore techniques for solving
sparse problems that greatly enhance computational efficiency. | | | Title: | Semidefinite Relaxations for Multistage Robust Optimization and Stochastic Programming | | Lead: | Dan Iancu,Doctoral
Candidate, Operations Research Center, MIT, 77 Massachusetts Ave.,
Cambridge MA 02139, United States of America, daniancu@mit.edu
| | Co-Author: | Dimitris Bertsimas,Boeing
Professor of Operations Research, Massachusetts Institute of
Technology, 77 Massachusetts Avenue, Bldg. E40-149, Cambridge MA 02139,
United States of America, dbertsim@mit.edu
| | | Pablo A. Parrilo,Professor, MIT, Stata Center, MIT, Cambridge, United States of America, parrilo@mit.edu
| | Abstract: | In
this work, we introduce a new framework for computing near-optimal
policies for multi-stage robust optimization and stochastic programming
problems, based on solving a single semi-definite programming
relaxation. We demonstrate the performance of the resulting policies
numerically, in the context of two classical inventory management
applications. | | | Title: | Models for Minimax Stochastic Linear Optimization Problems with Risk | | Lead: | Xuan Vinh Doan,Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge MA 02139, United States of America, vanxuan@mit.edu
| | Co-Author: | Dimitris Bertsimas,Boeing
Professor of Operations Research, Massachusetts Institute of
Technology, 77 Massachusetts Avenue, Bldg. E40-149, Cambridge MA 02139,
United States of America, dbertsim@mit.edu
| | | Karthik Natarajan,National University of Singapore, Department of Mathematics, Singapore 117543, Singapore, matkbn@nus.edu.sg
| | | Chung-Piaw Teo,National
University of Singapore, Department of Decision Sciences, Business
School, Singapore 117591, Singapore, bizteocp@ nus.edu.sg
| | Abstract: | We
study the minimax stochastic optimization problem with a moment-based
distribution class. We show that the model is tractable for problems
with random objective and some special ones with random right-hand
side. We provide explicit worst-case distributions and compare minimax
solutions with data-driven solutions under contaminated distributions.
Computational results show minimax solutions hedge against worst-case
distributions and provide lower variability in cost than data-driven
ones. | | |
|
Delete | | | 13:30 - 15:00 : Risk in Portfolio Decision Analysis |
| Chair: | Jeff Keisler,Associate Professor, UMass Boston, 100 Morrissey Blvd, Boston MA 02125, United States of America, Jeff.Keisler@umb.edu
| Title: | Managing a Portfolio of Risks | | Lead: | Jeff Keisler,Associate Professor, UMass Boston, 100 Morrissey Blvd, Boston MA 02125, United States of America, Jeff.Keisler@umb.edu
| | Co-Author: | Igor Linkov,Risk
and Decision Science Focus Area Lead, US Army ENgineer Research and
Development Center, 83 Winchester Str, Suite 1, Brookline MA 02446,
United States of America, Igor.Linkov@usace.army.mil
| | Abstract: | We
describe several key steps in applying DA to a portfolio of risks.
First, we frame the portfolio and map it to a portfolio of decisions.
Alternatives include allocation of funds to reduction activities for
each risk, but may be more specific, e.g., mitigation, amelioration,
diversification, and sharing. Risk interactions such as correlation and
causal relationships must be efficiently characterized. Value functions
are designed to consider significant losses across multiple dimensions.
| | | Title: | Using Portfolio Objectives to Define and Manage Portfolio Risk | | Lead: | Jack Kloeber,Kromite LLC, 12 Penns Trail, Newtown PA 18940, United States of America, jkloeber@kromite.com
| | Abstract: | In
R&D organizations, budget, talent, time, constrain the number and
size of R&D projects which can be resourced. Organizational
objectives drive us to choose which project strategies should be
funded. Since R&D is inherently risky, management needs a process
for taking portfolio risk, not project risk, into account when making
such decisions. We will discuss methods for accomplishing this, as well
give examples of lost value when portfolio risk is ignored. | | | Title: | A Simple Mean-risk Model with Behavioral and Prescriptive Flexibility | | Lead: | Alessandra Cillo,Assistant Professor, IESE, Avenida Pearson 21, Barcelona 08034, Spain, acillo@iese.edu
| | Co-Author: | Philippe Delquie,INSEAD, Boulevard de Constance, Fontainebleau, France, philippe.delquie@insead.edu
| | Abstract: | We
propose a behavioral Mean-Risk model that fulfills first and second
order stochastic dominance generalizing results on Mean-Gini, and the
axioms of Convex Risk Measures. It produces behavior intermediary
between Expected Utility and Rank-Dependent Utility. Model's
predictions in asset trading and allocation are provided. | | | Title: | Portfolio Optimization of Natural Resources with an Application to the Management of Forest Stands | | Lead: | Janne Kettunen,jkettunen@london.edu
| | Co-Author: | Ahti Salo,Professor,
Helsinki University of Technology, Systems Analysis Laboratory, P.O.
Box 1100, Espoo 02015, Finland, ahtisalo@cc.hut.fi
| | Abstract: | We
develop a stochastic optimization model for a forest owner who needs to
determine medium-term harvesting strategies under uncertainty about
timber prices. Risks are managed by applying conditional value at risk
and satisfying risk measures. The results suggest that extreme risks
can be significantly reduced without appreciable reductions in the
expected proceeds from timber sales. The results also suggest that risk
averse owners tend to harvest their forests earlier than risk neutral
owners. | | |
|
Delete | | | 13:30 - 15:00 : Computational Linear and Integer Programming |
| Chair: | Yan Xu,Analytical Solutions Manager, SAS Institute Inc., SAS Campus Drive, Cary, United States of America, Yan.Xu@sas.com
| Title: | Microsoft Solver Foundation | | Lead: | John Oberon,Director
of Program Management, One Microsoft Way, 4/2194, Redmond WA
98052-6399, United States of America, John.Oberon@Microsoft.com
| | Abstract: | Solver
Foundation is a pure, managed code runtime for mathematical
programming, modeling, and optimization. This .NET/CLR based framework
provides a rich set of tools, services, and engines.
We will focus on our computational integer programming effort - a
branch and cut solver based on Dual Simplex, and is designed to enable
64-bit and multi-core computation environments. We will discuss
advanced presolve, Gomory mixed integer cuts, mixed integer rounding
cuts, and local search heuristics. | | | Title: | Solving Linear Optimization Problems with MOSEK | | Lead: | Bo Jensen,MOSEK ApS, C/O Symbion Science park Fruebjergevj 3, Copenhagen, Denmark, bo.jensen@mosek.com
| | Abstract: | The software package MOSEK is capable of solving large-scale sparse
linear optimization problems using either an interior-point, a
primal simplex or a dual simplex algorithm. The aim of this talk is
to present the linear optimizers and the recent advances in their
implementation. Moreover, we will present numerical results
demonstrating the optimizers performance. | | | Title: | Cutting Planes in SAS MILP Solver | | Lead: | Amar Narisetty,SAS Institute, SAS Campus Drive, Cary, United States of America, Amar.Narisetty@sas.com
| | Co-Author: | Yan Xu,Analytical Solutions Manager, SAS Institute Inc., SAS Campus Drive, Cary, United States of America, Yan.Xu@sas.com
| | Abstract: | The
SAS MILP solver implements a branch-and-cut algorithm for solving large
scale mixed integer linear programs. In this talk, we give an overview
of the families of cutting planes currently incorporated in the SAS
MILP solver. These include, GMIC, MIR, Covers, Cliques, etc. We present
computation results to demonstrate the effectiveness and contribution
of each family of cutting planes in solving some well known instances.
| | | Title: | IBM ILOG CPLEX Technology Update | | Lead: | John Gregory,ILOG
CPLEX Product Manager, IBM ILOG Optimization, 889 Alder, Suite 200,
Incline Village NV 89451, United States of America, jgregor@us.ibm.com
| | Abstract: | This
talk will highlight the recent major enhancements in IBM ILOG CPLEX,
covering both solution speed and usability features. Details on MIP
benchmarking results will be provided. The latest information about the
integration of ILOG and its products into the greater IBM optimization
community will also be shared. | | |
|
Delete | | | 16:30 - 18:00 : Multivariate Polynomial Optimization: Theory and Algorithms |
| Chair: | Jiawang Nie,UCSD, 9500 Gilman Drive, La Jolla\, United States of America, njw@math.ucsd.edu
| Title: | Which Convex Sets are Expressible by Semidefinite Programming ? | | Lead: | J. William Helton,Professor, UCSD, 9500 Gilman Drive, La Jolla, United States of America, Helton@math.ucsd.edu
| | Co-Author: | Jiawang Nie,UCSD, 9500 Gilman Drive, La Jolla\, United States of America, njw@math.ucsd.edu
| | Abstract: | There
are three natural directions this problem can take. The first one is
what convex sets can be represented by linear matrix inequality (LMI).
The second direction is whether this can be done when the variables are
matrices of arbitrary dimensions.
The last one is what convex sets are LMI represented by adding
auxiliary variables, which is also called semidefinite programming
(SDP) representable. | | | Title: | A Convex Polynomial that Is not SOS-convex | | Lead: | Amir Ali Ahmadi,MIT, 195 Binney st., Apt. #4401, Cambridge MA 02142, United States of America, a_a_a@mit.edu
| | Co-Author: | Pablo A. Parrilo,Professor, MIT, Stata Center, MIT, Cambridge, United States of America, parrilo@mit.edu
| | Abstract: | The
algebraic notion of sos-convexity has recently been proposed as a
sufficient condition for convexity of polynomials based on semidefinite
programming. Motivated by its computational tractability, it has been
speculated whether sos-convexity is also a necessary condition for
convexity of polynomials. In this paper, we give a negative answer to
this question by presenting an explicit example of a trivariate
homogeneous polynomial of degree eight that is convex but not
sos-convex. | | | Title: | A New SDP Approach to the Max-cut Problem | | Lead: | Joao Gouveia,University
of Washington, Department of Mathematics Box 354350, Seattle WA 98105,
United States of America, jgouveia@u.washington.edu
| | Co-Author: | Monique Laurent,CWI, Kruislaan 413, 1098 SJ, Amsterdam, Netherlands, monique@cwi.nl
| | | Pablo A. Parrilo,Professor, MIT, Stata Center, MIT, Cambridge, United States of America, parrilo@mit.edu
| | | Rekha R. Thomas,University
of Washington, Department of Mathematics Box 354350, Seattle WA 98105,
United States of America, rrthomas@u.washington.edu
| | Abstract: | Using
sums-of-squares techniques we develop a new hierarchy of SDP
relaxations for the Max-Cut problem, solving an open question by Laszlo
Lovasz. | | | Title: | SDP Representation of Rational and Singular Convex Sets | | Lead: | Jiawang Nie,UCSD, 9500 Gilman Drive, La Jolla\, United States of America, njw@math.ucsd.edu
| | Co-Author: | J. William Helton,Professor, UCSD, 9500 Gilman Drive, La Jolla, United States of America, Helton@math.ucsd.edu
| | Abstract: | A
set is called SDP representable if it is expressible by some linear
matrix inequality via lifting variables. First, we will present a
general result: A set S defined by polynomial inequalities is SDP
representable if its boundary pieces are nonsingular and positively
curved. Second, we will present conditions for SDP representability
when S is defined by multivariate rational polynomial functions or its
boundary pieces have singularities. Specific examples will also be
shown. | | |
|
Wednesday Oct 14
| Delete | | | 08:00 - 09:30 : Wireless Networks 2 |
| Chair: | Ivan Guardiola,Assistant Professor, Missouri S&T, 600 W. 14th St, Rolla MO 65409, United States of America, guardiolai@mst.edu
| Title: | Control Overhead Reduction and Through Movement Awareness using GPS Information. | | Lead: | Ivan Guardiola,Assistant Professor, Missouri S&T, 600 W. 14th St, Rolla MO 65409, United States of America, guardiolai@mst.edu
| | Abstract: | This
presentation highlights a new approach of mitigating the correlated
effects of movement and multi-path fading on wireless ad hoc network
communication. The use of GPS and velocity estimation methods during
the route discovery phase result in more stable communication route
within specific time interval. This leads to an increase of scalability
as the control overhead is reduced. We present a new fundamental
approach to movement based route selection.
| | | Title: | GPS Link Exclusion Comparison In TCP and UDP Based MANETS | | Lead: | aaron phillips,Texas Tech University, 2320 A 18th Street, Lubbock TX 79401, United States of America, aaron.phillips@ttu.edu
| | Co-Author: | Timothy Matis,Texas
Tech University, Dept of Industrial Engineering, Box 43061, Lubbock TX
79409, United States of America, timothy.matis@ttu.edu
| | Abstract: | Work
done using GPS location information to exclude possibly weak links in a
route sending data packets has covered both UDP and TCP transport
protocols. The question raised is whether such a mechanism might be
transport-protocol specific. This research seeks to determine if the
GPS link exclusion method benefits one transport protocol more than the
other, or if this mechanism benefits the network independent of the
transport protocol being used. | | | Title: | Optimization Approaches to Wireless Sensor Network Design Problem | | Lead: | Hui Lin,Texas A&M University, 201 Zachary, College Station, United States of America, linhui@neo.tamu.edu
| | Co-Author: | Halit Uster,Associate Professor, Texas A&M University, 3131TAMU, college station TX 77843, United States of America, uster@neo.tamu.edu
| | Abstract: | We
present an integrated analytical modeling framework for wireless sensor
networks design incorporating topology control and routing decisions.
The optimization model attempts to promote energy efficiency with the
purpose of prolonging network lifetime. We develop efficient solution
procedures based on energy distribution characteristics and
decomposition approaches. We also present computational results on the
performance of the solution methods for test problem instances. | | | Title: | A Lagrangian Algorithm for the Capacitated Relay Network Design in Telecommunications | | Lead: | Panitan Kewcharoenwong,Texas A&M University, Industrial and System Engineering, College Station TX, United States of America, panitan@neo.tamu.edu
| | Co-Author: | Halit Uster,Associate
Professor, Texas A&M University, Industrial and Systems
Engineering, College Station TX, United States of America,
uster@tamu.edu
| | Abstract: | We
consider a multi-commodity flow network where the commodities are
relayed from origins to destinations through relay points. We provide a
mathematical model to determine the relay point locations, arc
selections, and data routing. We present a Lagrangian relaxation based
algorithm for its solution and computational results illustrating the
efficiency of the approach. | | |
|
Delete | | | 08:00 - 09:30 : Freight Planning & Policy |
| Chair: | Rajeev Namboothiri,CIRRELT - CRT, C.P. 6128, succ. Centre-ville, MONTREAL, Canada, rajeev@crt.umontreal.ca
| Title: | Using Operations Research to Support > California Low-Carbon Emission Policy formation | | Lead: | Changzheng Liu,University
of California at Davis, Dep. of Civil & Environmental Eng., Davis
CA 95616, United States of America, czliu@ucdavis.edu
| | Co-Author: | Yueyue Fan,Associate
Professor, UC Davis, Department of Civil Engineering, One Shields
Avenue, Davis CA 95616, United States of America, yyfan@ucdavis.edu
| | | David Greene,Corporate
Fellow, Oak Ridge National Laboratory, OAK RIDGE NATIONAL LABORATORY,
Oak Ridge, United States of America, dlgreene@ornl.gov
| | Abstract: | This
research studies the design and implementation of a feebate program in
California for Green House Gas (GHG) emission reduction in
Transportation sector by stimulating advanced vehicle technologies.
Feebate is a market policy which charges fees on relatively
high-emitting vehicles and gives rebates on low-emitting vehicles. A
nonlinear program is established to identify an optimal feebate policy
that balances the cost of technology and the requirement of related
regulations such as CAFE | | | Title: | Insights into Robust Optimization: Lessons from Different Applications and Methods | | Lead: | Lavanya Marla,lavanya@MIT.EDU
| | Co-Author: | Cynthia Barnhart,Associate
Dean for Academic Affairs, MIT, School of Engineering, Cambridge MA
02139, United States of America, cbarnhart@MIT.EDU
| | | Eleni Pratsini,IBM Research Zurich Research Lab, Ruschlikon, Switzerland, pra@zurich.ibm.com
| | | Alexander Rikun,MIT, 1 Amherst St. E40-149, Cambridge MA 02139, United States of America, arikun@mit.edu
| | | Gautier Staffer,IBM Research Zurich Research Lab, Ruschlikon, Switzerland, sta@zurich.ibm.com
| | Abstract: | In
this talk, we will share insights from the application of different
robust optimization approaches to the class of resource allocation
problems. Instances of resource allocation problems are extracted from
the finance, pharmaceutical and airline industries. We study the impact
of building robust solutions using different methods for these
applications. Through these instances, we improve upon our
understanding of different robust approaches, and their relationship
with data and recovery.
| | | Title: | Measuring Logistics Security for Rationalizing Counter-Risk Priority: An AHP-Based Case Study | | Lead: | Jung Ung Min,Assistant Professor, Inha University, Yonghyun 253, Incheon, Korea, Republic of, jumin@inha.ac.kr
| | Co-Author: | Minyoung Park,Assistant Professor, Inha University, Yonghyun 253, Incheon, Korea, Republic of, mypark@inha.ac.kr
| | Abstract: | To
improve the efficiency of logistics and ensure safe freight flow, a
comprehensive set of supply chain security initiatives have been
practiced throughout the world. Therefore, it is necessary to respond
immediately to security requirements. In this context, this study
visited security experts in Korea in order to assess the security level
of Incheon Port. Using AHP, this research derived the security items
with respect to the importance level and their priorities. | | | Title: | A Comprehensive Evaluation of Regional Freight Transportation Systems Using an Integrated Platform | | Lead: | Rajeev Namboothiri,CIRRELT - CRT, C.P. 6128, succ. Centre-ville, MONTREAL, Canada, rajeev@crt.umontreal.ca
| | Co-Author: | Teodor Crainic,CIRRELT-UQAM, C.P. 6128, succursale Centre-ville, Montreal QC H3C 3J7, Canada, theo@crt.umontreal.ca
| | | Jean Damay,SNCF, SNCF, Paris, France, damay@crt.umontreal.ca
| | | Michel Gendreau,Professor,
CIRRELT/Université de Montréal, C.P. 6128, succ. Centre-ville, Montréal
QC H3C 3J7, Canada, michel.gendreau@cirrelt.ca
| | Abstract: | In
this talk, we analyse the strategic national/regional planning of
multi-commodity multi-modal freight transportation systems using an
integrated evaluation platform, and present comprehensive results
examining the impact of planned and forecasted system modifications and
regulatory policies | | |
|
Delete | | | 11:00 - 12:30 : Green Energy III |
| Chair: | Panos Pardalos,University of Florida, 303 Weil Hall, P.O. Box 116595, Gainesville FL, United States of America, pardalos@ufl.edu
| Co-Chair: | Niko Iliadis,EnerCoRD, Plastira Street 4, Nea Smyrni, Athens 171 21, Greece, niko.iliadis@enercord.com
| | Steffen Rebennack,PhD
Candidate, University of Florida, 303 Weil Hall, P.O. Box 116595,
Gainesville FL 32611, United States of America, steffen@ufl.edu
| Title: | Including Wind in Power-System Siting and Capacity Expansion Models | | Lead: | Richard Chen,University of Michigan, IOE, Ann Arbor, United States of America, richchen@umich.edu
| | Co-Author: | Duncan Callaway,University of Michigan, SNRE, Ann Arbor, United States of America, dcall@umich.edu
| | | Amy Cohn,University of Michigan, 1205 Beal Avenue, Ann Arbor MI 48109, United States of America, amycohn@umich.edu
| | Abstract: | When
including wind in power-system design models, it is important to take
into account transmission losses, because wind is often cited far from
the load centers, unlike conventional power sources such as coal or
natural gas based generation. We present new models for siting and
capacity expansion planning that incorporate wind and the associated
transmission losses. We demonstrate how these models can be solved
using a variation of Benders Decomposition.
| | | Title: | Test-and-Prune: Designing Wind Farms with Probabilistic Constraints | | Lead: | Amy Cohn,University of Michigan, 1205 Beal Avenue, Ann Arbor MI 48109, United States of America, amycohn@umich.edu
| | Co-Author: | Duncan Callaway,University of Michigan, SNRE, Ann Arbor, United States of America, dcall@umich.edu
| | | Richard Chen,University of Michigan, IOE, Ann Arbor, United States of America, richchen@umich.edu
| | Abstract: | We
present models for designing networks of wind farms in which
probabilistic constraints on loss-of-load must be enforced. We
demonstrate the challenges of solving these models with traditional IP
techniques and introduce a new algorithm, which we call Test-and-Prune,
to overcome these challenges.
| | | Title: | Incorporating Renewables and Demand Response into Unit Committment Problems | | Lead: | Jayant Kalagnanam,Senior Manager, IBM T.J. Watson Research Center, Yorktown Hts NY 10598, United States of America, jayant@us.ibm.com
| | Abstract: | Many
utilities have begin to incorporate wind and solar energy as part of
their generation portfolio. Due to uncertainty from weather this leads
to uncertainty in generation sources which needs to be explitly modeled
in the unit committment problem. We study the stochastic unit
committment problem to solve for generation uncertainty.
| | | Title: | Optimization of Wind Farm Portfolios | | Lead: | Warren Powell,Professor, Princeton University, Sherrerd Hall 230, Princeton NJ 08544, United States of America, powell@princeton.edu
| | Co-Author: | Yintao (Alex) Sun,Princeton
University, Dept of Operations Research and Fin Engg, Princeton NJ
08544, United States of America, yintaos@Princeton.EDU
| | Abstract: | The
electricity from multiple wind farms can be combined on a single
electric power grid, making it possible to balance correlations in
output to produce a portfolio with lower overall volatility. We use
both a Markowitz model and a stochastic gradient algorithm to design
wind portfolios which mitigate the intermittent nature of wind by using
actual wind profiles which reflect spatial and temporal correlations.
Numerical experiments demonstrate the effectiveness of the strategy.
| | |
|
Delete | | | 11:00 - 12:30 : Optimization Techniques |
| Chair: | David Papp,Rutgers
University, 640 Bartholomew Rd, Center for Operations Research,
Piscataway 08854, United States of America, dpapp@rutcor.rutgers.edu
| Title: | Discrete Risk Optimization Models with p-Order Conic Constraints | | Lead: | Policarpio Soberanis,University of Iowa, 3131 Seamans Center, Iowa City IA 52242, United States of America, policarpio-soberanis@uiowa.edu
| | Co-Author: | Pavlo Krokhmal,Assistant
Professor, University of Iowa, 3131 Seamans Center, Iowa City IA 52242,
United States of America, krokhmal@engineering.uiowa.edu
| | Abstract: | We
present a class of risk-reward optimization models that reduce to
integer programming problems with p-order conic constraints. As an
illustration, a portfolio optimization application is considered. The
proposed solution approach relies on the developed polyhedral
approximations for p-order cones. Computational results of portfolio
optimization case studies are discussed. | | | Title: | Robust Regression using Semi-definite Programming | | Lead: | Dzung Nguyen,UIUC, 205 North Mathews Ave., Urbana IL 61801, United States of America, ngtridung@yahoo.com
| | Abstract: | The
robust regression problem is often formulated as the least trimmed
squares (LTS) problem where we want to find the best subset of
observations with the smallest sum of squared residuals. We show the
LTS problem is equivalent to a concave minimization problem, which is
very hard to solve. We resolve this difficulty by introducing the
maximum trimmed squares problem that finds the worst subset of
observations. This problem can be transformed into an SDP problem that
can be solved efficiently. | | | Title: | Shape-constrained Estimation of Multivariate Functions via Semidefinite Programming | | Lead: | David Papp,Rutgers
University, 640 Bartholomew Rd, Center for Operations Research,
Piscataway 08854, United States of America, dpapp@rutcor.rutgers.edu
| | Co-Author: | Farid Alizadeh,Professor, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854, United States of America, alizadeh@rutcor.rutgers.edu
| | Abstract: | Function
estimation problems often involve functions that must satisfy certain
shape constraints, which usually reduce to the nonnegativity of linear
functionals of the estimated function. If the estimator is a
multivariate spline, then these constraints are intractable; hence we
consider tractable restrictions involving weighted-sum-of-squares
cones. We present theoretical justifications of the proposed method,
applications, and computational results. | | |
|
Delete | | | 11:00 - 12:30 : Joint Session Optimization/Minority Issues: Branchwidth, Treewidth, and Integer Programming! Oh, my!! |
| Chair: | Illya Hicks,Associate Professor, Rice University, 6100 Main St. - MS 134, Houston TX 77005-1892, United States of America, ivhicks@rice.edu
| Title: | A Branch-and-price-and-cut Approach for Determining the Optimal Bramble Number | | Lead: | Sibel Sonuc,University of Florida, PO Box 116595, Gainesville, United States of America, sibel.bilge@ufl.edu
| | Co-Author: | Cole Smith,Associate
Professor, University of Florida, PO Box 116595, Gainesville FL 32611,
United States of America, j.cole.smith@gmail.com
| | Abstract: | In
this study, we investigate a methodology to find the bramble number of
a given graph. We investigate a branch-and-price-and-cut algorithm to
solve this problem. However, both columns and rows must be added to the
master problem at each iteration. We model the not-yet-generated rows
as hidden rows with unknown associated dual values. A dual value of
zero is valid for these rows, but the generation of degenerate (and
useless) columns can be avoided by examining a space of optimal dual
values. | | | Title: | Near Optimal Branch Decompositions for Linear Matroids | | Lead: | Illya Hicks,Associate Professor, Rice University, 6100 Main St. - MS 134, Houston TX 77005-1892, United States of America, ivhicks@rice.edu
| | Co-Author: | Jing Ma,graduate student, Stanford University, jm11.rice@gmail.com
| | Abstract: | The
notions of branch decompositions and branchwidth were introduced by
Robertson and Seymour in their proof of the Graph Minors Theorem.
Later, Dharmatilake extended these notions to matroids. In this vein,
we present a polynomial-time heuristic to compute near optimal branch
decompositions of linear matroids. The heuristic utilizes diffusion
regularization and techniques of partially-labeled classification. We
offer some theoretical and computational results. | | | Title: | Computational Results on the Cunningham-Geelen Algorithm for solving Integer Programs | | Lead: | Susan Margulies,Post-doc, Rice University, 6100 Main Street, Houston TX 77005, United States of America, susan.margulies@rice.edu
| | Co-Author: | Illya Hicks,Associate Professor, Rice University, 6100 Main St. - MS 134, Houston TX 77005-1892, United States of America, ivhicks@rice.edu
| | | Jing Ma,Graduate Student, Rice University, 6100 Main St. - MS 134, Houston TX 77005, United States of America, Jing.Ma@rice.edu
| | Abstract: | Consider
the integer program max(c^Tx : Ax = b, x >= 0,) where A is
non-negative and the column-matroid of A (denoted by M(A)) has constant
branch width. Cunningham and Geelen introduced a pseudo-polynomial time
algorithm for solving this integer program that takes a branch
decomposition T of M(A) as input. We report on computation results of a
C++ implementation of this algorithm. | | |
|
Delete | | | 12:45 - 14:15 : Stochastic Optimization I |
| Chair: | Medha Dhurandhar,Head
& Program Coordinator, Centre for Development of Advanced
Computing, Pune University Campus, Ganeshkhind Rd., Pune 411007, India,
mdhurandhar@gmail.com
| Title: | Pattern Discrete and Mixed Hit-and-run for Global Optimization and Mixed Integer Programming | | Lead: | Huseyin Mete,PhD
Candidate / Research Assistant, University of Washington, Industrial
and Systems Engineering, Box 352650, Seattle WA 98195-2650, United
States of America, mete@u.washington.edu
| | Co-Author: | Zelda Zabinsky,Professor,
University of Washington, Industrial and Systems Engineering, Box
352650, Seattle WA 98195-2650, United States of America,
zelda@u.washington.edu
| | Abstract: | We
develop Markov chain Monte Carlo samplers for neighborhood generation
in global optimization based on Hit-and-Run. We define Sphere and Box
Biwalks that are pattern based and easily implemented for discrete and
mixed domains bounded by linear constraints. The Markov chains converge
to a target distribution over sets in a polytope. We derive performance
bounds on mixing time for special cases that are polynomial in
dimension. We discuss impact to Improving Hit-and-Run for special cases
of MIP. | | | Title: | Convex Bernstein Polynomial Approximation on the Stochastic Resource Allocation Problem | | Lead: | Lijian Chen,Assistant
Professor, University of Louisville, 5241 Craigs Creek Dr, Louisville
KY 40241, United States of America, lijian.chen@louisville.edu
| | Abstract: | We
propose to solve large scale network resource allocation problem with
stochastic demands by fitting the expected objective by a sequence of
convex polynomials with non-negative coefficients and thereafter apply
Newton's method on it. We apply a Weierstrass-like theorem and showed
that if we can evaluate the expected appraisal function, we will reach
the arbitrary optimal by solving the new problem. When experimental
errors exist, we have the probabilistic convergence instead. | | | Title: | Semidefinite Programming Under Uncertainty | | Lead: | Yuntao Zhu,Arizona State University, PO Box 37100, Phoenix AZ 85069-7100, United States of America, yuntao.zhu@asu.edu
| | Co-Author: | K. A. Ariyawansa,Washington State University, Department of Mathematics, Pullman WA 99164, United States of America, ari@wsu.edu
| | Abstract: | In
this talk we introduce a new optimization paradigm termed Stochastic
Semidefinite Programming (SSDP) for dealing with uncertain data in
applications leading to semidefinite programs. The formulation of SSDP
is stressed as well as applications and solving algorithms. | | | Title: | The Distribution Problem for Stochastic Linear Programming | | Lead: | Sara Nourazari,PhD Student, University of Oklahoma, 202 W. Boyd, Rm 124, Norman OK 73019, United States of America, sara.n@ou.edu
| | Co-Author: | Hillel Kumin,University of Oklahoma, 202 W. Boyd, Rm 124, Norman OK 73019, United States of America, hkumin@ou.edu
| | Abstract: | Numerical
results for the distribution problem for stochastic linear programming
problem are very difficult to obtain. Using a Jacobian transformation
we obtain a new closed form expression for the cumulative distribution
function (CDF) of the maximum value of the objective function in a
stochastic linear programming problem in the case where either the
objective function coefficients or the right-hand side coefficients are
given by known probability distributions. | | | Title: | Efficient Algorithm Constructing Minimum Path Factors of Digraphs Minimizing Operational Cost | | Lead: | Medha Dhurandhar,Head
& Program Coordinator, Centre for Development of Advanced
Computing, Pune University Campus, Ganeshkhind Rd., Pune 411007, India,
mdhurandhar@gmail.com
| | Abstract: | We
present an efficient algorithm constructing all minimum path factors of
acyclic digraphs modeling real world problems. This involves generation
of pseudo-bipartite subdigraphs & edge-contraction along maximum
matching in the subdigraphs. This methodology gives flexible, pragmatic
solutions under realistic constraints for a wide variety of Industrial
applications like optimal resource scheduling for Project Management,
Logistics/Transport industry, Assembly line processing in Manufacturing | | |
|
Delete | | | 14:45 - 16:15 : Simulation and Optimization |
| Chair: | Jong-hyun Ryu,Purdue University, 315 N. Grant St., West Lafayette IN 47906, United States of America, ryuj@purdue.edu
| Title: | Large Scale Production Optimization using a MINLP Approach | | Lead: | Kashif Rashid,Research
Scientist, Schlumberger-Doll Research, One Hampshire Street, Cambridge
MA 02319, United States of America, krashid@slb.com
| | Co-Author: | Benoit Couet,Scientific
Advisor/Program Manager, Schlumberger-Doll Research, One Hampshire
Street, Cambridge MA 02139, United States of America, bcouet@slb.com
| | | Suleyman Demirel,PhD Candidate, University of Michigan, 701 Tappan Ave, Ann Arbor MI 48104, United States of America, sdemirel@umich.edu
| | Abstract: | A
methodology to treat large-scale surface network models for hydrocarbon
revenue maximization in the presence of various operating constraints
is presented. The control variables include continuous gas-lift
injection and discrete or continuous sub-surface chokes. As each
simulation is costly and derivatives are unavailable, an efficient
technique for handling such MINLP problems is proposed.
| | | Title: | Kriging Metamodeling in Simulation Optimization | | Lead: | Mehdi Zakerifar,PhD
Student, University of Louisville, Dept. of Industrial Engineering,
University of Louisville, Louisville KY 40292, United States of
America, m0zake01@louisville.edu
| | Co-Author: | Gerald Evans,Professor,
University of Louisville, Dept. of Industrial Engineering, University
of Louisville, Louisville KY 40292, United States of America,
gwevan01@louisville.edu
| | Abstract: | Kriging
is a geostatistical interpolation method that predicts unknown values
of a random function based on a weighted linear combination of all
values already observed. This technique has been widely used in areas
as diverse as geology, logistics, and manufacturing. In our approach,
we will define the Kriging metamodeling as a tool for simulation
optimization; and then we will compare Kriging methodology with the
other standard interpolation methods within an experiment. | | | Title: | A Screening Model to Explore Planning Decisions in Manufacturing Systems under Demand Uncertainty | | Lead: | Yingxia Yang,Massachusetts Institute of Technology, 550 Memorial Dr, Apt.11b3, Cambridge MA 02139, United States of America, yingxia@mit.edu
| | Co-Author: | Randolph Kirchain,Associate Professor, MIT, 77 Massachusetts Ave, E38-432, Cambridge MA 02139, United States of America, kirchain@mit.edu
| | | Richard Roth,Director,
Materials Systems Lab, MIT, 77 Massachusetts Ave, E38-435, Cambridge MA
02139, United States of America, rroth@mit.edu
| | Abstract: | This
research develops a method to design manufacturing systems for
uncertainty. It couples a screening model to identify designs with an
evaluation model to evaluate identified solutions. By using the
adaptive One Factor At a Time method with a Response Surface method and
simulation-based linear optimization, the screening model efficiently
explores a large decision space that is computationally intractable for
conventional optimization, which is demonstrated by a case study. | | | Title: | Multiobjective Simulation Optimization Using Adaptive Weighted Sum Method | | Lead: | Jong-hyun Ryu,Purdue University, 315 N. Grant St., West Lafayette IN 47906, United States of America, ryuj@purdue.edu
| | Co-Author: | Sujin Kim,Assistant Professor, National University of Singapore, 117576, Singapore, Singapore, iseks@nus.edu
| | | Hong Wan,Assistant Professor, Purdue University, 315 N. Grant Street, West Lafayette IN 47907, United States of America, hwan@purdue.edu
| | Abstract: | This
work proposes a new method for approximating Pareto front of
multi-objective simulation optimization problems where the explicit
forms of the objective functions are not available. The new scheme
iteratively approximates the objective functions using metamodels and
searches for the points on the Pareto front using weighted sum method.
The numerical results show that the proposed algorithm efficiently
generates evenly distributed points for various types of Pareto fronts. | | |
|
Delete | | | 16:30 - 18:00 : Threat Detection for Homeland Security |
| Chair: | Ron Billings,CEO, FABQ.com, 280 NE Cambridge Circle, Corvallis OR 97330, United States of America, profbillings@gmail.com
| Title: | Sensor Network Optimization for Threat Detection | | Lead: | Anton Molyboha,Postdoctoral
Associate, Stevens Institute of Technology, Castle Point on Hudson,
Hoboken NJ 07030, United States of America, amolyboh@stevens.edu
| | Co-Author: | Michael Zabarankin,Assistant
Professor, Stevens Institute of Technology, Castle Point on Hudson,
Department of Mathematical Sciences, Hoboken NJ 07030, United States of
America, mzabaran@stevens.edu
| | Abstract: | A
Markov chain approach to optimal coverage problem for threat detection
by a sensor network in a noisy environment has been developed. The
approach has been illustrated in application to diver detection in an
urban harbor. | | | Title: | Identifying Vulnerabilities Using Sensors Information | | Lead: | Monica M. De Marchi,Dra,
Institute for Advanced Studies/General Command for Aerospace
Technology, Rod dos Tamoios, km 5,5, Sao Jose dos Campos SP 12.228-001,
Brazil, monica@ieav.cta.br
| | Co-Author: | Maria Jose P. Lamosa,Dra,
Institute for Advanced Studies/General Command for Aerospace
Technology, Rod dos Tamoios, km 5,5, Sao Jose dos Campos SP 12.228-001,
Brazil, maju@ieav.cta.br
| | | Carmen Lucia R. Santos,Dra,
Institute for Advanced Studies/General Command for Aerospace
Technology, Rod dos Tamoios, km 5,5, Sao Jose dos Campos SP 12.228-001,
Brazil, carmenl@ieav.cta.br
| | Abstract: | In
this work methods of optimization are used to support the decision
making process by giving information about the coverage area by sensors
such as radars and cellular antennas. The aim is to provide indicators
to help the decision makers to identify vulnerabilities in a given
area. Some examples of scenarios where the research could be applied
and the methodology used until now are presented. | | | Title: | Discovering Radicalization Using Social Movement Theory, Argumentation Theory and Systems Dynamics | | Lead: | Dennis Engi,Professor, New Mexico State University, Box 30001/MSC 4230, Las Cruces NM, United States of America, engi@nmsu.edu
| | Abstract: | The
research described in this paper enabled analysts to develop a
conceptual framework for understanding, recognizing, and anticipating
the origins, dynamic mechanisms, perceptions, and social structures of
social reform movements in the homeland and in Diaspora communities.
The authors propose that Social Movement Theory combined with Systems
Dynamics and Argumentation Theory can provide an extensible foundation
for helping anticipate and potentially prevent terrorist actions. | | | Title: | Maritime Simulation Analysis of Radiological and Nuclear Threats | | Lead: | Daniel Faissol,Postdoctoral
Researcher, Lawrence Livermore National Laboratory, 7000 East Ave.,
L-227, Livermore CA 94550, United States of America, dfaissol@llnl.gov
| | Co-Author: | Matthew Dombroski,Lawrence Livermore National Laboratory, 7000 East Ave., L-229, Livermore, United States of America, dombroski2@llnl.gov
| | | Thomas Edmunds,Lawrence Livermore National Laboratory, 7000 East Av., L-184, Livermore, United States of America, edmunds2@llnl.gov
| | | Yiming Yao,Lawrence Livermore National Laboratory, 7000 East Ave., L-390, Livermore, United States of America, yao3@llnl.gov
| | Abstract: | We
summarize simulation analysis of radiological and nuclear threats from
small vessels that are directed towards, or transit, U.S. ports. Due to
the complex dynamics of search patrols in the harbor, benign vessels
that must be screened, radiation transport phenomena, detection
algorithms and concepts of operations (CONOPS), a simulation model is
required to evaluate the efficacy of a given countermeasure
architecture and enumerate design trade-offs.
| | | Title: | The Telegraph Patrol: Optimal Strategies for the Use of Randomness in Patrolling and Scanning | | Lead: | Ron Billings,CEO, FABQ.com, 280 NE Cambridge Circle, Corvallis OR 97330, United States of America, profbillings@gmail.com
| | Abstract: | Often
a fixed path needs to be patrolled (by a ship, aircraft, ground
vehicle, or video camera), but the movement along the path needs to be
difficult for a potential infiltrator to predict. If the patroller
reverses direction according to a Poisson process, this gives the least
information to an observer. We analyze infinite lines, closed loops, or
open line segments (and discuss more complicated scenarios); and derive
optimal values for reversal rates. | | |
|
Delete | | | 16:30 - 18:00 : Robust Optimization |
| Chair: | Apostolos Fertis,PhD Candidate, MIT, 70 Pacific Str, Apt # 927, Cambridge MA 02139, United States of America, afertis@mit.edu
| Title: | Using Robust Optimization in Banking Industries | | Lead: | Kevin Fleming,Scientist I, FICO, 200 Smith Ranch Road, San Rafael CA 94903, United States of America, kevinfleming@fico.com
| | Co-Author: | Brendan Del Favero,Senior Scientist, FICO, 200 Smith Ranch Road, San Rafael CA 94903, United States of America, BrendanDelFavero@fico.com
| | | Frank Elliott,Principal Scientist, FICO, 3661 Valley Centre Drive, San Diego CA 92130, United States of America, FrankElliott@fico.com
| | | Alkis Vazacopoulos,Vice President, FICO, 202 Parkway, Harrington Park NJ 07640, United States of America, alkisvazacopoulos@fico.com
| | Abstract: | Robust
optimization refers to optimization with non-probabilistic uncertainty
in the coefficients of the objective function and global constraints.
These problems arise in new or changing markets because of the lack of
historical data necessary to characterize the uncertainty as a
probability. We present an implementation of robust linear programming
that improves on previous techniques in both running time and
optimality, and can be used to solve real, current problems in banking
industries. | | | Title: | Robust Optimization in AIMMS | | Lead: | Marcel Hunting,Paragon Decision Technology, Schipholweg 1, Haarlem 2034 LS, Netherlands, Marcel.Hunting@aimms.com
| | Abstract: | The
AIMMS modeling language will be extended such that a robust
optimization model can be generated from any given deterministic model,
without the need to reformulate the deterministic model. By only
supplying additional attributes for selected parameters, variables and
constraints, AIMMS can generate both a deterministic and robust
optimization model from the same formulation. | | | Title: | A New, Intuitive and Industrial Scale Approach Towards Uncertainty in Supply Chains | | Lead: | Abhilasha Aswal,Associate
Technical Evangelist, Infosys Technologies Limited, 26/C Electronics
City, Hosur Road, Bangalore KA 560100, India,
abhilasha_aswal@infosys.com
| | Co-Author: | G. N. Srinivasa Prasanna,International
Institute of Information Technology Bangalore, 26/C Electronics City,
Hosur Road, Bangalore KA 560100, India, gnsprasanna@iiitb.ac.in
| | Abstract: | This
unique & industrial-scale robust-optimization approach bounds
parameters in polytopes built from economically meaningful linear
constraints. A set of parameter assumptions (SA) is a polytope.
Polytope relational algebra determines if different SAs are the same,
totally different, or have common assumptions. SA information content
is polytope volume, enabling comparison/equivalencing of SA's based on
information-content, comparison of information content of output w.r.t
input, etc. | | | Title: | An Operational Learning Approach to Portfolio Optimization | | Lead: | Ankit Jain,U.C. Berkeley, Berkeley CA 94709, ankit@ieor.berkeley.edu
| | Co-Author: | Andrew Lim,Associate
Professor, University of California (Berkeley), IEOR Department, 4177
Etcheverry Hall, University of California, Berkeley CA 94720-1777,
United States of America, lim@ieor.berkeley.edu
| | | J. George Shanthikumar,UC Berkeley, Berkeley, United States of America, jgshant@ieor.berkeley.edu
| | Abstract: | We
consider mean variance portfolio optimization problem. Classical
approaches are known to perform poorly out of sample in the presence of
estimation error. We introduce a new approach that guarantees a better
out of sample performance than classical one. We explore the link
between our approach and minimum norm portfolio. We reformulate the
problem as a semidefinite program and show numerical results. | | | Title: | Robust Maximum Likelihood | | Lead: | Apostolos Fertis,PhD Candidate, MIT, 70 Pacific Str, Apt # 927, Cambridge MA 02139, United States of America, afertis@mit.edu
| | Co-Author: | Dimitris Bertsimas,Boeing
Professor of Operations Research, Massachusetts Institute of
Technology, 77 Massachusetts Avenue, Bldg. E40-149, Cambridge MA 02139,
United States of America, dbertsim@mit.edu
| | | Omid Nohadani,MIT, 77 Massachusetts Ave, E40, Cambridge MA 02139, United States of America, nohadani@mit.edu
| | Abstract: | We
use robust optimization to define robust maximum likelihood estimators
that deal with uncertainty. We model errors both as deterministic and
stochastic variables. In case of stochastic variables, we prove that
the resulting optimization over measures problem has the same solution
as an optimization over deterministic decision variables problem. We
develop efficient algorithms to compute the robust estimators for the
multivariate normal distribution and show their effectiveness
numerically. | | |
|
Delete | | | 16:30 - 18:00 : Algorithmic Developments in Stochastic Optimization II |
| Chair: | Nan Kong,Assistant Professor, Purdue University, West Lafayette IN 47907, United States of America, nkong@purdue.edu
| Co-Chair: | Lewis Ntaimo,Assistant Professor, Texas A&M University, 3131 TAMU, College Station TX 77843, United States of America, ntaimo@tamu.edu
| Title: | Fenchel Decomposition for Stochastic Integer Programming | | Lead: | Lewis Ntaimo,Assistant Professor, Texas A&M University, 3131 TAMU, College Station TX 77843, United States of America, ntaimo@tamu.edu
| | Abstract: | In
this talk, we present a new cutting plane method for two-stage
stochastic integer programs called Fenchel decomposition (FD). FD is
based on a new class of valid inequalities termed, FD cuts, which are
based on Fenchel cutting planes in integer programming. We consider FD
cuts based on both the first- and second-stage variables, and based
only on the second-stage variables. Preliminary computational results
with instances from the literature will be presented. | | | Title: | Risk Classification Approach Through Convex Optimization | | Lead: | Vladimir Bugera,Kammerdiner Consulting, 16031 N 31st AVE, Phoenix AZ 85053, United States of America, vladimir@bugera.com
| | Co-Author: | Stan Uryasev,University
of Florida, Dept. of Industrial and Systems Engineer, 303 Weil Hall,
P.O. Box 116595, Gainesville FL 32611-6595, United States of America,
uryasev@ufl.edu
| | Abstract: | We
consider an optimization approach for multi-class classification. The
optimization problem is formulated as minimization of a penalty
function built with quadratic separating functions. It is reduced to
linear programming problem for finding parameters of optimal
classification. We apply this approach to evaluate risks in several
financial applications, and compare our methodology with conventional
techniques. | | | Title: | Algorithmic Development on a Class of Stochastic Quadratic 0-1 Programs | | Lead: | Nan Kong,Assistant Professor, Purdue University, West Lafayette IN 47907, United States of America, nkong@purdue.edu
| | Co-Author: | Zhen Zhu,Purdue University, West Lafayette IN 47907, zzhu@purdue.edu
| | Abstract: | We,
in this paper, study a class of two-stage stochastic quadratic
programming problems with 0-1 variables on both stages. We apply a
branch-and-fix framework and adapt various decomposition methods,
together with a number of linearization techniques within this
framework. Analytical and computational results will be presented for
the comparison of different methods. | | |
|
|