2016 INFORMS Annual Meeting Program

306 / 561

INFORMS Nashville – 2016
306
TC12
104B-MCC
New Results on Nonconvex Optimization
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Daniel Bienstock, Columbia University, 500 W 120th St,
New York, NY, 10027, United States,
Co-Chair: Daniel Bienstock, Columbia University, Departments of IEOR
and APAM, Columbia University, New York, NJ, 10027, United States,
1 - Centerpoints: A Link Between Optimization And
Convex Geometry
Amitabh Basu, Johns Hopkins University, ,
Timm Oertel
We introduce a concept that generalizes several different notions of a
“centerpoint” in the literature. We develop an oracle-based algorithm for convex
mixed-integer optimization based on centerpoints. Further, we show that
algorithms based on centerpoints are “best possible” in a certain sense. Motivated
by this, we establish several structural results about this concept and provide
efficient algorithms for computing these points.
2 - On Decomposability Of Multilinear Sets
Alberto Del Pia, University of Wisconsin-Madison,
Aida Khajavirad
We consider the Multilinear set defined as the set of binary points satisfying a
collection of multilinear equations. Such sets appear in factorable reformulations
of many types of nonconvex optimization problems, including binary polynomial
optimization. In this talk, we study the decomposability properties of Multilinear
sets. Utilizing an equivalent hypergraph representation, we derive necessary and
sufficient conditions under which a Multilinear set is decomposable based on the
structure of pair-wise intersection hypergraphs. Finally, we propose a polynomial-
time algorithm to optimally decompose a Multilinear set into simpler subsets.
3 - An FPTAS For Minimizing Some Indefinite Quadratics Over The
Integer Points In A Polyhedron In Fixed Dimension
Robert Hildebrand, IBM Research,
Although integer linear programming is an NP-Hard problem, Lenstra showed
that in fixed dimension the problem can be solved in polynomial time. On the
other hand, the problem of minimizing a quartic polynomial objective function
over the the integer points in polyhedra is NP-Hard even in dimension 2. The
complexity of minimizing quadratic and cubic polynomials in fixed dimension
remains an open question. As a step in this direction, we will present an FPTAS
for minimizing some quadratic polynomials in fixed dimension.This is joint work
with Robert Weismantel and Kevin Zemmer.
TC13
104C-MCC
Recent Advances in Computational Optimization
Sponsored: Optimization, Computational Optimization and Software
Sponsored Session
Chair: Gonzalo Munoz, Columbia University, 500 W. 120th Street,
IEOR Department, New York, NY, 10027, United States,
1 - Low-rank/sparse-inverse Decomposition
Victor Fuentes, University of Michigan, Ann Arbor, MI,
United States, , Jon Lee
A well-known matrix decomposition problem is to split an input matrix into
sparse and low-rank components. We look at decomposing an input matrix as the
sum of a matrix having a sparse inverse and a low-rank matrix. One approach
that we have developed is a convex SDP approximation. Also, employing the
Woodbury matrix identity, we establish another framework for attacking the
problem. Our numerical results demonstrate that: (1) our proposed methodology
is useful and practical, (2) our method leads to a means for generating good test
instances for algorithms that we are developing for the problem, and (3) a direct
generalization of the recovery theorem for the ordinary version of the problem is
unlikely.
2 - Improving The Randomization Step In Feasibility Pump
Andres Iroume, Georgia Institute of Technology,
Santanu Subhas Dey,
Marco Serpa Molinaro, Marco Serpa Molinaro
In this work, we modify the randomization step in feasibility pump. This step is
used when staling is detected in order to avoid cycling. In our version, we use a
WALKSAT-type method that automatically detects sparse structures. We prove
theoretical upper bounds on the running time (to the best of our knowledge for
the first time for feasibility pump) and provide computational results that show a
considerable reduction both in terms of numbers of iterations and computing time
when applied to MIPLIB instances.
3 - A Branch-and-bound Algorithm For The Facility Location Problem
With Random Utilities
Eduardo Moreno, Universidad Adolfo Ibáñez, Santiago, Chile,
, Alexandre S Freire, Wilfredo Yushimito
The maximum capture problem with random utilities seeks to locate new facilities
in a competitive market such that the captured demand of users is maximized,
assuming that each individual chooses among all available facilities according to a
random utility model. We also introduce a new branch-and-bound algorithm
based on a column generation scheme for solving the original problem. Extensive
computational experiments are presented, benchmarking the proposed approach
with other linear and non-linear relaxations of the problem. Computational
experiments show that our algorithm is competitive with all other methods as
there is no method which outperforms the others in all instances.
4 - Submodular Path Inequalities For Capacitated Lot-sizing With
Inventory And Backlogging Bounds
Birce Tezel, University of California-Berkeley, Berkeley, CA,
94720, United States, , Alper Atamturk
We consider single item capacitated lot-sizing problems with backlogging (CLSB)
where the maximum production, inventory and backlogging values are bounded.
Using the underlying fixed-charge network structure of CLSB, we derive strong
submodular path inequalities. These inequalities generalize flow cover
inequalities for single node relaxations of CLSB. The computational results
suggest that submodular path inequalities are quite effective in solving CLSB
instances when used in a branch-and-cut algorithm.
TC14
104D-MCC
Sustainable and Responsible Supply
Chain Management I
Sponsored: Energy, Natural Res & the Environment I
Environment & Sustainability
Sponsored Session
Chair: Sandra D Eksioglu, Clemson University, Clemson, SC,
United States,
1 - Valuing A Cellulosic Biofuel Project Considering
Supply Uncertainty
Guiping Hu, Iowa State University, Yihua Li,
Chung-Li Tseng, Wei-Chung Miao
Iowa intends to invest in cellulosic biofuel production to expand its renewable
fuels consumption. The yield of main feedstock, corn stover, fluctuates due to
climate change, especially the rainfall amount. Dual sourcing is a possible strategy
to mitigate the supply uncertainty, which in our case is the option of investing in
growing dedicated energy crops as an additional supply source. A real options
approach is used to analyze the optimal investment timing and benefits of the
dual sourcing.
2 - Lot Sizing With Emission Dependent Demand
Gokce Palak, Shenandoah University,
We extend economic lot sizing models to maximize profit and minimize
emissions. This model captures the tradeoffs between supplier and mode selection
decisions, as well as profits and emissions. We analyze impacts of price and
emissions sensitive demand on the replenishment decisions.
3 - A Competitive Supply Chain Framework With Sustainable
Environmental Policies
Min Yu, University of Portland, Portland, OR, United States,
, Jose Cruz
We develop a competitive supply chain network model with multiple firms, each
of which produces a differentiated product. Multiple production, storage, and
transport mode options are allowed. In order to control firms’ environmental
emissions, the policy-maker seeks to decide the optimal policy instrument.
Numerical illustrations provide managerial insights and policy implications.
TC12