
Session A
Multiobjective optimization (MO) concerns the optimization of more than 1 objective at the same time. In case the objectives and the constraints are convex, we are dealing with convex MO for which it holds that the Pareto front is convex as well. Sandwich algorithms use an inner and an outer approximation that are iteratively updated to approximate the Pareto front of the convex MO up to epsilon precision, where the maximum distance between the inner and the outer approximation determines the direction in which the algorithm searches. One of the first to consider such a sandwich algorithm is Solanki et al. (1993) where they use weighted sum scalarization to expand the inner approximation. Using the inner normals as weights, one is only guaranteed to find efficient points when the inner normals are positive. Although nonpositive weights are helpful to expand the inner approximation, one starts to describe part of the nonPareto part of the convex MO as well. In our work we consider a modification of the criterion space, the MCS, which aims to describe less of the nonPareto part than the formulation of Solanki. This saves solving uninformative LPs. Furthermore, we provide a proof that shows that for the MO with linear objectives and constraints, the MOLP, it is possible to obtain all Pareto points using weighted sum scalarization as long as the considered criterion space is (made) bounded and contains all Pareto points. At last, we present a new measure to approximate the distance between the inner and the outer approximation which is less computationally heavy than the exact measure of Solanki et al. (1993) and less involved than of Craft et al. (2006).
We consider the Continuous EnergyConstrained
Scheduling Problem (CECSP), introduced by Nattaf et al. (2014). A set of jobs has
to be processed on a continuous resource. Each job requires a given
total amount of resource during its execution. We want to find a schedule such
that: a job does not start before its release time, is completed before its
deadline, and respects its lower and upper bounds on resource consumption
during processing. Our objective is to minimize the total weighted completion
time. We look at the case where both the resource and time are continuous. We
assume that there is no 6efficiency function influencing resource consumption.
We present a hybrid local search algorithm that exploits a decomposition of the
problem, where we use local search to find an order of events (start/completion
of a job), and for a given order determine optimal start and completion times
as well as resource consumption using an eventbased LP formulation. We perform
computational experiments to compare the performance of our algorithm with
exact approaches and to show its ability to deal with larger problem sizes. Our
approach can be extended to deal with piecewise linear resource availability
functions, explicit precedence relations and linear efficiency functions.
We introduce a novel approach, called the
ReformulationPerspectification Technique (RPT), to
obtain convex approximations of nonconvex continuous optimization problems. RPT
consists of two steps: the reformulation step generates redundant nonconvex
constraints from pairwise multiplication of the existing constraints; the perspectification step then convexifies the nonconvex
components by using perspective functions. RPT extends the existing
ReformulationLinearization Technique (RLT) in two ways. First, it can multiply
constraints that are not linear or not quadratic, and thereby obtain tighter
approximations than RLT. Second, it can also handle more types of nonconvexity
than RLT. Session B
For the first time a modelbased
evolutionary algorithm is presented for a reallife Home Health Care Routing
and Scheduling Problem (HHCRSP). The algorithm
generates routes consisting of care activities jointly with the underlying
shift schedule, while taking into account the
qualification levels. The performance is optimized in terms of travel time,
time window waiting time and shift overtime. The algorithm is a novel extension
of the permutation GenePool Optimal Mixing Evolutionary Algorithm. Numerical
experiments, using reallife data, show that the algorithm performs close to
optimal for small instances, and outperforms schedules from a case study,
leading to efficiency gains of 41%. Furthermore, it is shown that the
modelbased evolutionary algorithm performs better than a more traditional
evolutionary algorithm, which demonstrates the importance of learning and
exploiting a model to guide the optimization in HHCRSP.
Stochastic models are traditionally
built on the assumption that the probability distributions of the driving
random variables are known, whereas a distributionfree perspective assumes
that these distributions are only partially known. Distributionally robust
analysis seeks to calculate the worstcase model performance over the set of
distributions satisfying this partial information. For most stochastic models,
finding this worstcase scenario requires convex optimization methods, which
are strongly linked to the generalized moment problem. However, in this talk,
we emphasize specific methodological challenges for stochastic models with
multiple random variables that are independent and identically distributed (i.i.d.). Applying existing optimization methods then
becomes difficult, or even impossible, since the resulting optimization problem
is no longer convex. We will connect these challenges with
the problem of finding tight bounds for waiting time moments in the GI/GI/1
queue, as one of many examples from applied probability with i.i.d. random variables as input. For example, one of the
most notorious (and still open) problems in queueing theory is to compute the
worstpossible expected waiting time of the GI/GI/1 queue under meanvariance
constraints for the interarrival and servicetime distributions. In this
setting, the extremal distribution has only been determined numerically as the
solution of a nonconvex optimization problem. We will instead address the extremal
queue problem by measuring dispersion in terms of Mean Absolute Deviation (MAD)
as a substitute for the more conventional variance. Using MAD instead of
variance alleviates the computational intractability of the extremal GI/GI/1
queue problem, which arises from the i.i.d. property,
enabling us to state the worstcase distributions explicitly. Combined with
classical random walk theory, we then obtain explicit expressions for the
bestpossible upper bounds for all moments of the waiting time.
Despite measures
to reduce congestion, both recurrent patterns (e.g., rush hours) and
nonrecurrent events (e.g., traffic incidents) cause large delays in highway
networks with important economic implications. In this talk, we will introduce the Markovian Velocity Model (MVM), a framework capable of incorporating both effects.
The model uses an environmental background process that tracks the random and
(semi)predictable events affecting the vehicle speeds in a highway network.
The resulting continuoustime model, which allows for correlation between
velocities on the arcs, is highly flexible. This flexibility can be employed to
fit the model on a reallife network. The fitted model can then be used to
predict travel time distributions and, as a result, provide guidance for travelers in this highway network.
Heterogeneity
and compatibility relations between jobs and servers
are becoming ubiquitous in cloud computing platforms due to data locality and
network topology constraints. These features strongly diverge from the inherent
symmetry of the supermarket model as the baseline scenario for performance
benchmarking in parallelserver systems. We focus in particular on redundancy scheduling systems which exploit
the variability of service times of a job on different servers. More
specifically we gain insight in the performance of these systems with
compatibility constraints in limiting regimes via productform stationary
distributions. For instance in a heavytraffic regime,
the system achieves complete resource pooling and exhibits the same behavior across a broad range of scenarios. 