|
|
Tuesday | Abstracts of presentations by PhD students II
Session A
The Branch-and-Bound algorithm is a well-known
method for solving integer linear programs. In the worst case this algorithm
achieves an exponential running time, but until recently very little about was
known about its behaviour on random instances. We show
that for certain classes of random ILP's, the running
time is only polynomial. To prove this result we solve
a discrepancy problem for random matrices using Fourier analysis.
Railway operators typically employ large
numbers of drivers and guards, and are interested in
providing them with fair and attractive working conditions. At Netherlands
Railways (NS), the largest passenger railway operator in the Netherlands, this
challenge is addressed through the use of
Sharing-Sweet-and-Sour rules, which specify a fair allocation of sweet
(attractive) and sour (unattractive) work over the different crew bases. While
these rules are currently implemented at the crew base level and in the tactical
planning phase, NS is considering formulating these rules at the individual
level and in the operational planning phase. This gives rise to a new problem,
which we call the operational railway crew planning problem with individual
Sharing-Sweet-and-Sour rules. We propose a rolling horizon approach based on a
column generation heuristic to solve this problem, which is
able to achieve high satisfaction levels of the individual rules on
several large real-life instances from NS. Our approach is not only relevant to
railway operators, but can be applied in any setting
where work must be fairly allocated to individuals in a dynamic fashion.
Strategic long term energy
planning requires a large scope and long time horizon.
The parameters of such models are often subject to much uncertainty and
ignoring this uncertainty may lead to faulty or even disastrous decision
making. In this talk I will explain the concept of robustness analysis, and argue for its practical usefulness over the
more conventional sensitivity analysis. We extend the methodology to a
multistage adaptive setting and apply the methodology to a hydrogen supply
chain network design problem.
The cone of copositive
matrices COP_n is the set of nxn
real symmetric matrices M for which the quadratic form x^TMx
is nonnegative over the nonnegative orthant. Optimizing a linear function over
the copositive cone is a hard problem in general since it permits to capture
many hard combinatorial problems, including the maximum stable set problem. In
this talk we first consider several hierarchies of approximations for COP_n that are based on sums of squares of polynomials and
we present some links among them. Based on this we revisit the copositive
formulation for the stability number of a graph and show new results on a
conjecture proposed by de Klerk and Pasechnik in
2002. We finish with some open questions and new advances about the exactness
of the sums of squares approximations for COP_n. Session B
Trust and fairness regarding information and revenue
sharing are key factors in the development of the sharing economy. We study a
contracting problem between a platform and its content supplier, in which the
platform can either offer to manage the content on behalf of the supplier and
share revenue afterwards (contract A), or let the supplier manage his own
content and report trade, while charging him a commission fee per reported
trade (contract B). At the contracting stage, the platform decides how much revenue
to share in contract A and the commission fee in contract B. In addition, the
platform offers a revenue forecast in contract A to help the supplier better
predict the revenue when his content is managed by someone else (i.e., the
platform). The supplier decides which contract to accept based on utility
maximization, considering his trust in the platform's disclosed revenue
forecast in contract A and his fairness concern over the revenue-sharing ratios
in both contracts. By developing a browser contracting game and getting 71
management-major students to play as the platform, we first demonstrate that
our model has practical potentials. Using game-theoretical models, we then
derive the optimal contracting mechanism in different scenarios. We show that
the optimal contracts diverge into two categories: (1) a fair contract where
the platform shares more of the content revenue with the supplier who has a
higher fairness sensitivity; and (2) a trustworthy contract where the platform
does not inflate or deflate its revenue forecast during the contracting
process, considering its deception cost. We also find that the supplier with a
higher fairness sensitivity will under-report the content revenue in the
contract where he manages his own content. When facing the supplier who has a
smaller deception cost, and is thus prone to cheat when reporting revenue, the
platform will charge a larger commission fee. However, the larger the
commission fee, the more the supplier will cheat.
The Carry-Over Effect in scheduling measures how
many different pairs of consecutive opponents occur among all players in a
competition. If this number is low, the Carry-Over Effect is said to be high,
which is considered undesirable. A balanced Round Robin competition has every
pair of consecutive opponents appear exactly once, but not for every number of
players N, such a schedule exists. In fact, only when
N is 20, 22, or a power of 2, such balanced schedules have been constructed.
The limiting factor in finding new balanced schedules is among others the sheer
number of possible Round Robin schedules. By restricting focus to specific
types of promising schedules, we go on the hunt for these balanced schedules
for large N.
The 2-opt heuristic is a
simple local search heuristic for the Travelling Salesperson Problem (TSP).
Although it usually performs well in practice, its worst-case running time is
poor. Attempts to reconcile this difference have used smoothed analysis, in which
adversarial instances are perturbed probabilistically. We are interested in the
classical model of smoothed analysis for the Euclidean TSP, in which the
perturbations are Gaussian. This model was previously used by Manthey \& Veenstra, who obtained smoothed complexity
bounds polynomial in $n$, the dimension $d$, and the perturbation strength
$\sigma^{-1}$. However, their analysis only works for
$d \geq 4$. The only previous analysis for $d \leq 3$ was performed by Englert, Roglin
& Vocking, who used a different perturbation
model which can be translated to Gaussian perturbations. Their model yields
bounds polynomial in $n$ and $\sigma^{−d}$, and
super-exponential in $d$. As no direct analysis existed for Gaussian
perturbations that yields polynomial bounds for all $d$, we perform this
missing analysis. Along the way, we improve all existing smoothed complexity
bounds for Euclidean 2-opt.
Data scarcity in developing countries often
significantly complicates the use of analytics to address development
challenges. One of the most fundamental data structures needed in operations
management is digitized road data; a poorly digitized road network
significantly reduces our ability to optimize, for instance, trade of
micro-enterprises (SDG 8) and placement of hospitals (SDG 3). Here, we
introduce a method that accurately extends and combines large, existing road
network representations, for regions with sparse geospatial data. Our method
significantly improved the digital road network for smallholder farmers in
Indonesia, and, in a case study of optimized geospatial accessibility to
healthcare in Timor-Leste, it improved the detection of people located in the
vicinity of a hospital. |
