Abstracts
Thursday, December 8, 2016
10:00 - 10:25
Sparsest cut in planar graphs, maximum concurrent
flows and their connections with the max-cut problem
F. Barahona
, M. Baiou
We study the sparsest cut problem when the
"capacity-demand" graph is planar, and give a
combinatorial algorithm. In this type of graphs there
is an edge for each positive capacity and also an edge
for each positive demand. We extend this result to
graphs with no $K_5$ minor. We also show how to find a
maximum concurrent flow in these two cases. We use
ideas that had been developed for the max-cut problem,
and show how to exploit the connections among these
problems.
11:00 - 11:25
Mathematical models with a polynomial number of
variables and constraints for some NP-hard
combinatorial optimization problems in graphs
N. Maculan
, Laura Bahiense, Arthur Besso
We present integer linear models with a polynomial
number of variables and constraints for combinatorial
optimization problems in graphs: optimum elementary
cycles (whose traveling salesman problem), optimum
elementary paths even in a graph with negative cycles,
and optimum trees (whose Steiner tree problem)
problems. Computational results for the the Steiner
tree problem are also presented.
11:25 - 11:50
Computational Study of Some Valid Inequalities for
k-Way Graph Partitioning
M. Anjos
, Vilmar Jefte Rodrigues de Sousa,
Sebastien Le Digabel
We consider the maximum k-cut problem that consists in
partitioning the vertex set of a graph into k subsets
such that the sum of the weights of edges joining
vertices in different subsets is maximized. We focus
on identifying effective classes of inequalities to
tighten the semidefinite programming relaxation. We
carry out an experimental study of four classes of
inequalities from the literature: clique, general
clique, wheel and bicycle wheel. We considered
multiple combinations of these classes and tested them
on both dense and sparse instances for different
values of k. Our computational results suggest that
the bicycle wheel and wheel are the strongest
inequalities for k=3, and that for greater k, the
wheel inequalities are the strongest by far.
11:50 - 12:15
Relay Location and Network Design
H. Yaman
, aris Yildiz, Oya Ekin Karasan
Relays are regenerators extending the reach of optical
signals in telecommunications networks; they are
strategic locations where exchange of drivers, trucks
or mode of transportation takes place in
transportation networks or refuelling/recharging
stations extending the reach of alternative fuel
vehicles in green transportation. With different
names and characteristics, relays play a crucial role
in the design of telecommunications and transportation
networks. We study the network design problem with
relays and present a multi-commodity flow formulation
and a branch-and-price algorithm to solve
it. Motivated by the practical applications we
investigate the special case where each demand has a
common origin. In this special case, we can show that
there exists an optimal design that is a tree. Using
this fact, we replace the multi-commodity flow
formulation with a tree formulation enhanced with
Steiner cuts. Employing a branch-and-price-and-cut
algorithm on this formulation, we are able to further
extend computational efficiency.
14:20 - 14:45
Maman les petits bateaux
J. F. Maurras
About the power of sailing engines.
14:45 - 15:10
Reducing some graph parameter via minimal edge contractions
C. Picouleau
Let d and k be two given integers, and let G be
a graph. Can we reduce a parameter of G by at least
d via at most k edge contractions?
We investigate the computational complexity of these
problems for fixed values of d and k and for some
subclasses of graphs. The parameter we are interested
are the independence number, the clique number, or the
chromatic number.
15:10 - 15:35
The Stochastic Shortest Path Problem: A polyhedral
combinatorics perspective
G. Stauffer
The Stochastic Shortest Path problem (SSP) is a
natural extension of the deterministic shortest path
problem whereby traversing an 'arc' may now lead to
several destinations with different probabilities. In
this setting, vertices are called states and arcs are
called actions. The goal is to decide in each time
step and each state which action to take so as to
converge to a predefined target with probability one
over an infinite time horizon. Taking an action has a
cost and we wish to find a policy that minimizes the
average cost over all possible realizations. The SSP
was studied thoroughly by Bertsekas and Tsitsiklis
(1991) and later by Bertsekas and Yu (2016) and it is
well understood when there is no nonpositive cost
'transition cycles'. In this talk we give a fresh look
at the problem from a polyhedral combinatorics
perspective. We study the natural linear programming
relaxation of the problem and we show that actually
standard methods also converge when there is no
negative cost transition cycles. This closes the gap
with the deterministic shortest path problem.
15:35 - 16:00
Extended (Weird) Flow based Models for the (PC)ATSP
L. Gouveia
, P. Pesneau, M. Ruthmair,
D. Santos
There are many ways of modelling the Asymmetric
Traveling Salesman Problem (ATSP) and the related
Precedence Constrained ATSP (PCATSP). In this talk we
present new formulations for the two problems that can
be viewed as resulting from combining precedence
variable based formulations, with network flow based
formulations. As suggested in [1], the former class of
formulations permits to integrate linear ordering
constraints. The motivating formulation for this work
is a complicated and "ugly" formulation that results
from the separation of generalized subtour elimination
constraints presented in [2] (see also [1]). This so
called "ugly" formulation exhibits, however, one
interesting feature, namely the "disjoint sub- paths"
property that is further explored to create more
complicated formulations that combine two (or three)
"disjoint path" network flow based formulations and
have a stronger linear programming bound. Some of
these stronger formulations are related to the ones
presented for the PCATSP in [3] and can be viewed as
generalizations in the space of the precedence based
variables. Several sets of projected inequalities in
the space of the arc and precedence variables and in
the spirit of many presented in [1] are obtained by
projection from these network flow based
formulations. Computational results will be given for
the ATSP and PCATSP to evaluate the quality of the new
models and inequalities.
References:
[1] L. Gouveia and P. Pesneau. On extended
formulations for the precedence constrainted
asymmetric traveling salesman problem. Networks,
48(2):77{89, 2006.
[2] L. Gouveia and J. M. Pires. The asymmetric
travelling salesman problem: On generalizations of
disaggregated Miller-Tucker-Zemlin
constraints. Discrete Applied Mathematics,
112:129{145, 2001.
16:30 - 16:55
High-dimensional risk-constrained dynamic asset allocation via
Markov stochastic dual dynamic programming
M. Poggi
, Davi Valadão, Thuener Silva,
Dynamic portfolio optimization has a vast literature
exploring different simplifications by virtue of
computational tractability of the problem. Previous
works provide solution methods considering unrealistic
assumptions, such as no transactional costs, small
number of assets, specific choices of utility
functions and oversimplified price dynamics. Other
more realistic strategies use heuristic solution
approaches to obtain suitable investment policies. In
this work, we propose a high-dimensional
risk-constrained dynamic asset allocation model and
efficiently solve it using the stochastic dual dynamic
programming algorithm. We consider multiple assets,
transactional costs and a Markov factor model for
asset returns. We present results for a realistic
100-asset model guaranteeing a sufficiently small
optimality gap with high probability. To the best of
our knowledge, this is the first systematic approach
for solving realistic high-dimensional dynamic
stochastic asset allocation problems.
16:55 - 17:20
Vertex k-Separator Problem
F. Furini
Abstract: Given an undirected graph, a Vertex k-Cut
(VKS) is a subset of the vertex set such that, when
the VKS is removed from the graph, the remaining
vertices can be partitioned into k subsets that are
pairwise edge-disconnected. The problem of finding the
minimum size VKS is called Vertex k-Cut Problem
(VKSP). We give a proof that VKSPis NP-Hard. We
present a compact Integer Linear Programming
formulation for the problems and investigate the
associated polytopes. We also present extensive
formulations, for which we derive a column generation
and a branching scheme. Extensive computational
results prove the effectiveness of the proposed
methods and of the theoretical analysis.
17:20 - 17:45
The split-demand one-commodity pickup-and-delivery
travelling salesman problem
J.J. Salazar Gonzalez
, Beatriz Santos
This talk is related with the article published by
Kerivin, Lacroix, Mahjoub and Quilliot in 2008 on the
splittable pickup and delivery problem with
reloads. We give a mathematical model, an exact
branch-and-cut algorithm and a matheuristic approach
for a new vehicle routing problem that generalizes the
capacitated vehicle routing problem with split demands
and some other variants recently addressed in the
literature.
Friday, December 9, 2016
09:15 - 09:40
Tight MIP formulations for unit commitment and
production planning problems with bounded up/down
times
M. Queyranne
, L. Wolsey
We study tight mixed integer programming formulations
for unit commitment and production planning problems
with bound constraints on the lengths of on- and
off-intervals. The resulting optimization problems
admit a general Dynamic Programming (shortest path)
formulation which leads to tight extended formulations
with a number of binary variables that is quadratic in
the number of time periods. We present tight
formulations with linear numbers of binary variables,
derived from a network dual formulation based on new
integer cumulative variables, that treats time-varying
lower and upper bounds on interval lengths. This in
turn leads to more general results, including simpler
proofs of known tight formulations, for problems with
just lower bounds. We also present some open
problems.
09:40 - 10:05
Some mathematical gems in Distance Geometry
L. Liberti
, Carlile Lavor
Distance geometry focuses on the concept of distance
rather than points and lines. Its fundamental problem
asks to draw a weighted graph in a given K-dimensional
Euclidean space, so that each edge is drawn as a
segment with length equal to the weight, and it has
applications to many fields of science and engineering
(e.g. protein folding, wireless networks, robotic
control, nanostructures and more). Distance geometry
results are scattered throughout the whole history of
mathematics starting with the Greeks. I will present
some of those I find most beautiful.
10:05 - 10:30
Distance Transformation for Network Design Problems
E. Uchoa
, A.R. Mahjoub, M. Poss,
L. Simonetti
We propose a new way to construct extended
formulations a large for class of network design
problems. The approach is based on a transformation
that maps any graph into a layered graph according to
a given distance function. While graphs induced by
binary vectors are mapped to isomorphic graphs, those
induced by fractional vectors are mapped to less
connected graphs, where some vertices are
split. Hence, simple connectivity inequalities in the
layered graph may cut off fractional vectors that were
feasible for similar inequalities in the original
graph. Experiments over instances of the Steiner
Forest and Survivable Network Design problems show
very significant gap reductions over the state-of-the
art formulations.
11:00 - 11:25
The Polyhedral Lens
A. Sebo
I would like to recall to and share with Ridha and the
audience some simple old and new examples of the use
of polyhedral combinatorics for solving purely
combinatorial problems.
11:25 - 11:50
On the Convex Piecewise Linear Unsplittable
Multicommodity Flow Problem
B. Fortz
, Luís Gouveia, Martim Joyce-Moniz
We consider the problem of finding the cheapest
routing for a set of commodities over a directed
graph, such that: i) each commodity flows through a
single path, ii) the routing cost of each arc is given
by a convex piecewise linear function of the load
i.e. the total flow) traversing it.
We propose a new mixed-integer programming formulation
for this problem. The linear relaxation of this
formulation gives an optimal solution for the single
commodity case, and produces very tight linear
programming bounds for the multi-commodity
case.
We also derive new valid inequalities for the compact
basic model based on the projection of the extended
formulation.
11:50 - 12:15
Connectivity with Ridha
M. Baiou
I will present my work with Ridha on survivable
network design along with some souvenirs and personal
appreciations.
12:15 - 12:40
Reduced-size formulations for metric and cut polyhedra
in sparse graphs
V. H. Nguyen
, M. Minoux, D.P. Nguyen
Given a graph G=(V,E) of n vertices and m edges, we
consider the metric cone MET(G) and the metric
polytope METP(G) defined on the real space indexed by
E. These polyhedra are relaxations of several
important problems in combinatorial optimization such
as the max-cut problem and the multicommodity flow
problem. They are known to have non-compact
formulations via the cycle inequalities in the
original space inline image and compact (i.e.,
polynomial size) extended formulations via the
triangle inequalities defined on the complete graph of
n vertices. In this talk, we show that one can reduce
the number of triangle inequalities to O(nm) and still
have extended formulations for MET(G) and METP(G). We
also present several extensions of the result for
special graphs and for graph partitioning problem.
14:30 - 14:55
Min Cuts with Mahjoub and McCormick
S.T. McCormick
, Ridha Mahjoub and others...
I have worked with Ridha Mahjoub and others for 20
years on a variety of network optimization problems,
all related to min cuts of various types. I will
survey these results, which include the 2-edge
connected subgraph problem with bounded rings, max
flow and min cut with bounded-length paths, separation
algorithms for single-machine scheduling with
precedence constraints, and strongly polynomial bounds
for multiobjective and parametric global minimum cuts
in graphs and hypergraphs.
14:55 - 15:20
A Matheuristic for the Multicommodity Fixed-Charge
Network Design Problem
S. Hanafi
, Bernard Gendron, Raca Todosijevic
We propose an efficient iterative linear
programming-based heuristic for solving the
Multicommodity Fixed-Charge Network Design
problem. The computational results show that the
approach is competitive, finding more best solutions
than any other heuristic of the current
state-of-the-art.
15:20 - 15:45
Campaign planning optimization @ OM Partners
D. Huygens
OM Partners is a leading provider of supply chain
software, with the OMP Plus planning and scheduling
platform embedded with different optimization
techniques. In this talk, we first present various
kinds of problems that manufacturing companies are
facing (lotsizing, job sequencing, facility
location,...), before going into the specifics of
campaign planning. Two cases coming from the chemical
industry are highlighted further: the so-called "small
bucket" and "large bucket" cases. Finally, we give
some hints on how these industrial-size problems can
be tackled in practice by the use of mathematical
programming... and more.
16:15 - 16:40
Optimization in Mechanism Design
M. Pinar
Mechanism design is an area of micro-economic theory
where optimization is very useful. We give a very
simple introduction to optimization in mechanism
design using the simple problem of the sale of an
object between a seller and a buyer. The buyer has a
valuation (drawn from a discrete set) of the object
unknown to the seller. The seller wants to design a
selling mechanism that will maximize his/her expected
revenue. It is customary to assume that the
probability distribution of the values is known to the
seller. We relax this assumption and examine the
problem from a robustness perspective under a
worst-case optimization lens. Several extensions and
research directions will be pointed out.
16:40 - 17:05
A business dinner problem
F. Meunier
, Alejandra Estanislao
We are given suppliers and customers, and a set of
tables. Every evening of the forthcoming days, there
will be a dinner. Each customer must eat with each
supplier exactly once, but two suppliers may meet at
most once at a table. The number of customers and the
number of suppliers who can sit together at a table
are bounded above by fixed parameters. What is the
minimum number of evenings to be scheduled in order to
reach this objective? This question was submitted by a
firm to the Junior company of a French engineering
school some years ago. We provide lower and upper
bounds, proven optimal solutions with closed-form
expressions for some cases, and many conjectures.
