Goal setting | EPFL Graph Search

Goal setting involves the development of an action plan designed in order to motivate and guide a person or group toward a goal. Goals are more deliberate than desires and momentary intentions. Therefore, setting goals means that a person has committed thought, emotion, and behavior towards attaining the goal. In doing so, the goal setter has established a desired future state which differs from their current state thus creating a mismatch which in turn spurs future actions. Goal setting can be guided by goal-setting criteria (or rules) such as SMART criteria. Goal setting is a major component of personal-development and management literature. Studies by Edwin A. Locke and his colleagues, most notably, Gary Latham have shown that more specific and ambitious goals lead to more performance improvement than easy or general goals. The goals should be specific, time constrained and difficult. Vague goals reduce limited attention resources. Unrealistically short time limits intensify the dif

The power of adaptivity in source identification with time queries on the path

Victor Cyril L Lecomte, Gergely Odor, Patrick Thiran

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, and unknown edge weights

w(e)

for

e\in E

, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean

1

and variance

\sigma^2

. An algorithm then attempts to identify

v^*

by querying nodes

q \in V

and being told the length of the shortest path between

q

and

v^*

in graph

G

weighted by

w

. We consider two settings: \emph{non-adaptive}, in which all query nodes must be decided in advance, and \emph{adaptive}, in which each query can depend on the results of the previous ones. Both settings are motivated by an application of the problem to epidemic processes (where the source is called patient zero), which we discuss in detail. We characterize the query complexity when

G

is an

n

-node path. In the non-adaptive setting,

\Theta(n\sigma^2)

queries are needed for

\sigma^2 \leq 1

, and

\Theta(n)

for

\sigma^2 \geq 1

. In the adaptive setting, somewhat surprisingly, only

\Theta(\log\log_{1/\sigma}n)

are needed when

\sigma^2 \leq 1/2

, and

\Theta(\log \log n)+O_\sigma(1)

when

\sigma^2 \geq 1/2

. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process.

2022

Modeling Supply Chain Disruptions: A Network Flow Approach

René Yves Glogg

Globalization, outsourcing and cost optimization have all contributed to increased supply chain vulnerability, yet our understanding of effective mitigation strategies remains limited. In our research, we study the effects of disruptions on supply chain networks. To do so, we develop in the first research project a bilevel optimization model to analyze supply chain disruptions in a production setting. This results in a convex network flow problem in which total production cost is minimized under a chance constraint. This chance constraint imposes a bound on the regret of disrupted scenarios with high pre-determined probability, where this regret is defined as a cost surplus which results from a comparison between a reactive setting, where we consider the disruption unknown until it occurs, and an anticipative setting, which assumes the disruption scenario to be known at the beginning of the planning horizon. A generalized Benders decomposition approach which makes use of the problem structure is developed to solve the problem efficiently. In the second research project we study a similar model in which an additional chance constraint on service level is introduced to account for demand uncertainty. We derive an approximation of this model and derive a bound on the approximation error. This approximation model is then solved with the same Benders decomposition procedure as the first model discussed. We obtain managerial insights from both models by means of numerical experimentation. We demonstrate a relationship between the stochastic demand and service level requirements. Moreover, we observe that unused production capacity is a key driver for mitigation inventory. In the last research project we shift our focus towards gaining a more holistic understanding of the supply chain network disruption literature. The number of articles written in the area has increased significantly in the last few years, and with the advent of the Covid-19 pandemic the interest in the area has expanded even further. We perform a literature review with a particular focus on recognizing research gaps. We observe a surprising lack of articles studying assembly supply chains, despite their ubiquity in real world applications. A similar lack of articles is observed in the area of multi-product supply chains as well. Finally, in light of the ongoing Covid-19 pandemic we shift our attention towards the disruptive effect of pandemics on supply chains. We observe that most of the mathematical models of supply chain networks under disruptions discussed in the literature are incapable of accounting for the fact that pandemics disrupt several aspects of supply chain networks simultaneously. Moreover, we observe that a large number of articles studies problems stemming directly from real world applications. The resulting models are often challenging to solve mathematically, so we perform a comprehensive study of solution methods used in the supply chain network literature and highlight multi-objective optimization as an area of utmost importance for current and future research.

EPFL2021

Scalable and Efficient Comparison-based Search without Features

Daniyar Chumbalov, Matthias Grossglauser, Lucas Maystre

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generates noisy answers. First, we consider the non-blind setting where these features are accessible. We propose a new Bayesian comparison-based search algorithm with noisy answers; it has low computational complexity yet is efficient in the number of queries. We provide theoretical guarantees, deriving the form of the optimal query and proving almost sure convergence to the target t. Second, we consider the blind setting, where the object features are hidden from the search algorithm. In this setting, we combine our search method and a new distributional triplet embedding algorithm into one scalable learning framework called LEARN2SEARCH. We show that the query complexity of our approach on two real-world datasets is on par with the non-blind setting, which is not achievable using any of the current state-of-the- art embedding methods. Finally, we demonstrate the efficacy of our framework by conducting an experiment with users searching for movie actors.

2020

The power of adaptivity in source identification with time queries on the path

Victor Cyril L Lecomte, Gergely Odor, Patrick Thiran

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, and unknown edge weights

w(e)

for

e\in E

, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean

1

and variance

\sigma^2

. An algorithm then attempts to identify

v^*

by querying nodes

q \in V

and being told the length of the shortest path between

q

and

v^*

in graph

G

weighted by

w

G

is an

n

-node path. In the non-adaptive setting,

\Theta(n\sigma^2)

queries are needed for

\sigma^2 \leq 1

, and

\Theta(n)

for

\sigma^2 \geq 1

. In the adaptive setting, somewhat surprisingly, only

\Theta(\log\log_{1/\sigma}n)

are needed when

\sigma^2 \leq 1/2

, and

\Theta(\log \log n)+O_\sigma(1)

when

\sigma^2 \geq 1/2

. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process.

2022

Modeling Supply Chain Disruptions: A Network Flow Approach

René Yves Glogg

EPFL2021