2016 INFORMS Annual Meeting Program

21 / 561

INFORMS Nashville – 2016
21
SA14
2 - High Communication Efficiency Subgraphs
Vladimir Stozhkov, University of Florida, Gainesville, FL,
United States, Alexander Veremyev,
Oleg A Prokopyev
We introduce a new clique relaxation model which is based on the notion of
communication efficiency. The communication efficiency is assumed to be a non-
increasing function of pair-wise distances in a graph. We prove that the
corresponding maximization problem is NP-hard and present effective exact
algorithms to solve it.
3 - Approximating The Maximum Edge Weight Clique Problem Using
A Continuous Formulation
Seyedmohammadhossein Hosseinian, Texas A&M University, 2027
Emerging Technologies Building, Mail stop 3131, College Station,
TX, United States, Dalila B M M Fontes,
Sergiy Butenko
The Maximum Edge Weight Clique (MEWC) problem, defined on an undirected
and weighted graph, is to find a clique whose sum of edge weights is maximized.
This work presents a continuous formulation for the MEWC problem, along with
a heuristic based on solving the continuous form over a n dimensional
hypersphere, where n is the number of vertices of the graph. Results of the
algorithm on some benchmark instances are also presented.
SA12
104B-MCC
Algorithms, Polyhedra and Games
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Swati Gupta, Massachusetts Institute of Technology, Cambridge,
MA, United States,
1 - Algorithms For Stable Matching With Imperfect Transfer
Of Utility (ITU)
Rajan Harish Udwani, Massachusetts Institute of Technology,
, James B Orlin
The classical stable matching and utility transfer problems (also the dual of the
assignment problem), are two extreme cases of the imperfect utility transfer
problem, where we wish to find a stable matching in a bipartite graph, while
allowing imperfect/lossy transfer of utility across matched pairs. In case of
complete loss (or no transfer), we recover the former and in absence of loss we
get the latter. We develop a novel combinatorial algorithm for this generalized
stable matching problem under imperfect transfer of utility, when the loss
function is linear. The model was inspired by a recent paper of Galichon et al.
(2016).
2 - Polyhedral Study Of A Generalization Of The Continuous
Mixing Set
Haochen Luo, Texas A&M University, College Station, TX,
United States, Kiavash Kianfar
We report our progress on polyhedral study of a generalization of the continuous
mixing set. We provide facet-defining valid inequalities and discuss how they can
be used to generate cuts for well-known problems such as lot-sizing.
3 - Learning Combinatorial Structures
Swati Gupta, Massachusetts Institute of Technology, Cambridge,
MA, United States, , Michel X Goemans,
Patrick Jaillet
To find optimal strategies for dueling algorithms, we consider two online learning
methods: multiplicative weights update (MWU) and online mirror descent
(OMD). We first show how to simulate MWU over vertices of polytopes in R^m
(e.g. spanning trees, bipartite matchings), in time poly(m) under fast generalized
counting oracles (even if approximate). Next, we solve a well-known
computational bottleneck of computing projections for the OMD by giving novel
algorithms for separable convex minimization over base polymatroids (e.g. for
spanning trees, truncated permutations, subset of experts). These results extend
to applications in stochastic optimization, game theory and machine learning.
SA13
104C-MCC
Global Optimization: Algorithms and Applications
Sponsored: Optimization, Global Optimization
Sponsored Session
Chair: Emily Speakman, University of Michigan, MI, United States,
1 - Strong Relaxations For Optimal Power Flows
Pascal Van Hentenryck, University of Michigan,
, Carleton Coffrin, Hassan Hijazi
This talk reviews recent progress in convex relaxations of the power flow
equations, which combines the SDP relaxation, the QC relaxations, bound
tightening, and valid inequalities. Computational results on state-of-the-art
benchmarks are presented.
2 - Branching Point Selection For Trilinear Terms
Emily Speakman, University of Michigan, 2222 Fuller Court,
Apt 702A, Ann Arbor, MI, 48105, United States,
, Jon Lee
The case of having three or more expressions multiplied together (each expression
being possibly complex itself) occurs frequently in global-optimization models.
For these “trilinear terms,” we present some analytic results regarding the choice
of branching point and branching variable in the context of spatial branch-and-
bound, and we compare our results to common practice in software. In obtaining
the “best” branching point or variable we use n-dimensional volume as a
comparison measure. Using volume as a measure gives a way to analytically
compare formulations and corresponds to a uniform distribution of the optimal
solution across a relaxation.
3 - Virtuous Smoothing For Global Optimization.
Daphne Skipper, US Naval Academy, ,
Jon Lee
Virtually all exact solvers for global-optimization (GO) rely on NLP solvers, both
to generate good feasible solutions and to solve relaxations. Convergence of most
NLP solvers requires that functions be twice continuously differentiable. Yet many
models naturally utilize functions with some limited non-differentiability. One
approach to handle limited non-differentiability is via smoothing. We propose a
method, mostly aimed at (concave) root functions ($f(x)=x^p$, with $0<p<1$)
that provides a tighter lower bound than the obvious shift ($g(x)=(x+\epsilon)^p-
\epsilon^p$), and is smooth and globally concave, so it works well with local and
global solvers.
SA14
104D-MCC
Operations Research Approaches to Plant Breeding
Invited: Agricultural Analytics
Invited Session
Chair: Lizhi Wang, Iowa State University, Ames, IA, United States,
1 - Resource Allocation In Trait Introgression – A Markov Decision
Process Approach
Ye Han, Iowa State University,
Lizhi Wang, William D Beavis, John N Cameron
Plant breeding companies continuously improve their cultivars through trait
introgression projects, which are usually constrained with budgets and deadlines.
In this presentation, we formulate the optimal allocation of money and time
resources as a Markov decision process, in which the breeder incurs a cost for
each progeny produced and receives a reward for producing an ideal progeny by
the deadline. We will share preliminary results on a hypothetical trait
introgression project and discuss future research opportunities.
2 - Maximizing Quantitative Traits In The Mating Design Problem
Susan R Hunter, Purdue University, West Lafayette, IN, United
States, , Benjamin McClosky
We consider a version of the mating design problem in which breeders allocate a
breeding budget to a set of parent pairs to maximize the expected maximum trait
observed in the progeny population. In this context, the only parent pairs that
receive nonzero breeding budget at optimality in the mating design problem lie on
a Pareto set. Since the performance of each parent pair is assessed through Monte
Carlo simulation, identifying the Pareto set is a bi-objective simulation
optimization problem. We derive an asymptotically optimal simulation budget
allocation to estimate the Pareto set of parent pairs. This estimated Pareto set is
used as an input to the mating design problem, which is an integer program.