2016 INFORMS Annual Meeting Program

461 / 561

INFORMS Nashville – 2016
461
2 - A Reduced-space Algorithm For Minimizing L1-regularized
Convex Functions
Tianyi Chen, Johs Hopkins University,
We present a new method for minimizing the sum of a convex function and an
l1-norm regularizer. The main features of the new method include: (i) an
evolving set of indices corresponding to variables that are predicted to be nonzero
at a solution; (ii) a reduced-space subproblem defined in terms of the predicted
support; (iii) conditions that determine how accurately each subproblem must be
solved; (iv) a computationally practical condition that determines when the
predicted support should be updated; and (v) a reduced proximal gradient step
that ensures sufficient decrease. We prove a convergence guarantee for our
method and demonstrate its efficiency on a large set of model prediction
problems.
3 - R-linear Convergence Rate Of A Limited Memory Steepest
Descent Method
Wei Guo, Lehigh University,
We provide some theoretical convergence results for a limited memory steepest
descent (LMSD) method, proposed by Fletcher, when minimizing strictly convex
quadratics. First, we show a finite termination property for the algorithm when
there are duplicate eigenvalues. However, our main result shows an R-linear
convergence rate for the algorithm when minimizing a strictly convex quadratic
of any dimension with any limited memory history length. This extends the R-
linear convergence rate of the Barzilai Borwein “two-point step size” method
which uses information from only the previous iteration.
WD18
106A-MCC
Business Apps
Contributed Session
Chair: Kiel Michael Martin, USAF, 8940 Rochester Dr, Colorado
Springs, CO, 80920, United States,
1 - An Operational Model To Support Cotton Trade In India
Sundaravalli Narayanaswami, I I M, Ahmedabad, 380015, India,
Narasimhan Ravichandran
Cotton Corporation of India (CCI) is a government agency created to regulate the
market dynamics of cotton trade in India, (a cotton surplus country) to promote
and protect the economic interest of cotton growing farmers in India. When there
is a demand supply imbalance, CCI operates by appropriate price intervention and
procurement of the quantity available to stabilize price. The procured quantity is
sold by CCI at an appropriate time to maximize the economic value. The
operational expenses are reimbursed by the Union Government. We develop and
present simulation based models to facilitate negotiation between the government
and CCI on this activity.
2 - Internet Of Things And Smart City
Michael Chuang, SUNY New Paltz, 1 Hawk Drive, New Paltz, NY,
12561, United States,
Internet of Things have emerged as an enabler in various domains for facilitating
business or operations such as its application in smart cities. In this preliminary
study, we will review various scenarios where internet of things show potentials
in smart city applications, and also opportunities and challenges for Internet of
Things to be developed in this area.
3 - Connected Vehicle Analytics For In Vehicle Air
Quality Management
Yimin Liu, Mobility Analytics Manager, Ford Motor Company,
One American Road, Dearborn, MI, 48121, United States,
, Yu Chen, Jinjing Yang, Oleg Gusikhin,
Omar Makke, Jeff Yeung
This talk presents a concept of cloud-based system for in-cabin air quality
management. It leverages SmartDeviceLink technology to seamlessly integrate
smartphone apps with Ford SYNC infotainment system and allow
programmatically manage vehicle HVAC (Heating, Ventilation and Air
Conditioning) settings. This approach allows integrating advanced connected car
technologies, portable after-market sensors and cloud-based analytics into climate
control loop.
4 - Sustaining The Drone Enterprise
Kiel Michael Martin, Assistant Professor, USAF,
8940 Rochester Dr, Colorado Springs, CO, 80920, United States,
, Dan Richmond, John Swisher
The Remotely Piloted Aircraft (RPA), colloquially labeled the “drone,” has become
iconic of American military campaigns this century. The most salient question
concerning these aircraft at the Pentagon today is operational, not ethical: given
increasing global demand, how can the United States Air Force (USAF) produce
and retain sufficient numbers of pilots to fly these aircraft? As part of a recent
effort by the Secretary of Defense to stabilize the RPA enterprise, we developed a
dynamic manpower projection model, quantifying the potential impact of myriad
initiatives and directly informing new, Air Force-wide RPA policy.
WD19
106B-MCC
Advances in Mixed-Integer Programming Theory
and Algorithms
Sponsored: Computing
Sponsored Session
Chair: Adolfo Raphael Escobedo, Arizona State University, Brickyard
Engineering (BYENG) 553, 699 S Mill Ave, Tempe, AZ, 85281,
United States,
1 - Extensions Of Subadditive Duality For Conic Mixed-integer
Programs
Diego Moran, Universidad Adolfo Ibañez, ,
Burak Kocuk
In a recent paper it was proven that the subadditive dual for mixed-integer conic
program is a strong dual under a strict feasibility requirement. In this paper, we
generalize this result by exploring alternative sufficient conditions when strict
feasibility is not present. In particular, we prove that in the case of essential strict
feasibility and in the case of bounded feasible region, the subadditive dual has
zero duality gap. Moreover, we show that the dual is solvable when essential
strict feasibility holds while the solvability of the dual problem cannot be
guaranteed for bounded feasible regions. Finally, we discuss a relationship
between strong duality and cut generating functions.
2 - The Hamiltonian P-median Problem: Complexity And Algorithms
Erick Moreno-Centeno, Department of Industrial and Systems
Engineering, Texas A&M University, ,
Ahmed Mohamed Marzouk, Halit Uster
Given an undirected graph, G, the Hamiltonian p-median problem is to find p
cycles partitioning G with minimum cost. This problem is NP-hard for any given
value of p; however, the problem’s actual difficulty depends on the value of p.
Similarly, the state-of-the-art algorithms outperform each other (or fail
altogether) depending on the value of p. We give some insights on these
observations. This work is in collaboration with Halit Uster and Ahmed Marzouk,
both from Southern Methodist University.
3 - A Quadratic Relaxation For A Dynamic Knapsack Problem With
Stochastic Item Sizes
Daniel Blado, H. Milton Stewart School of Industrial and Systems
Engineering, Georgia Institute of Technology,
We examine the stochastic knapsack problem with random item sizes that are
realized upon each attempted insertion. The process aims to maximize expected
profit and ends after a failed insertion. We investigate dynamic programming-
based LP bounds and their gap with the optimal adaptive policy. Our relaxation
involves a quadratic value function approximation that encodes interactions
between remaining items. We compare the bound to the best known
pseudopolynomial bound and contrast their corresponding policies with two
greedy policies. We conclude that the quadratic bound is theoretically more
efficient than the pseudopolyomial bound yet empirically competitive in value
and runtime.
4 - Routing Optimization With Time Windows Under Uncertainty
Yu Zhang, Northeastern University, Shenyang, China,
, Roberto Baldacci, Melvyn Sim,
Jiafu Tang
We study an a priori Traveling Salesman Problem with Time Windows under
uncertain travel times. We propose a decision criterion for articulating service
levels that takes into account both the probability of lateness and its magnitude,
and can be applied in contexts where either the distributional information of the
uncertain travel times is fully or partially known. The criterion has the
computationally attractive feature of convexity that enables us to formulate and
solve the problem more effectively. Particularly, we obtain in some cases closed-
form solutions to the Benders subproblems.
WD19