Publications associées à Iterated local search

Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature rec ...

Association for the Advancement of Artificial Intelligence (AAAI)2023

Large-scale traffic signal control and multimodal network design

Dimitrios Tsitsokas

Traffic congestion constitutes one of the most frequent, yet challenging, problems to address in the urban space. Caused by the concentration of population, whose mobility needs surpass the serving capacity of urban networks, congestion cannot be resolved ...

EPFL2022

A note on the integrality gap of the configuration LP for restricted Santa Claus

Klaus Jansen, Lars Rohwedder

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

ELSEVIER2020

A Computational Method for Identifying the Optimum Buffer Size in the Era of Zero Defect Manufacturing

Dimitrios Kyritsis, Ali Boujemaoui, Foivos Psarommatis Giannakopoulos

Decreasing defects, waste time, meeting customer demand and being adaptable are the goals of a Zero Defect Manufacturing (ZDM) strategy. Scheduling is an important tool to perform that. It should take in account buffer size allocation. In this study, a met ...

SPRINGER INTERNATIONAL PUBLISHING AG2020

Combinatorial optimization of Dedicated Bus Lane layout in urban networks with dynamic congestion

Nikolaos Geroliminis, Dimitrios Tsitsokas, Anastasios Kouvelas

Transit priority based in exclusive right-of-way is a low-cost way of improving transit service by minimizing delays caused by interaction with other vehicles. This effect can increase the share of public transit against private cars in the mode preference ...

2020

A new wake model and comparison of eight algorithms for layout optimization of wind farms in complex terrain

Fernando Porté Agel, Roberto Brogna

Layout optimization of wind farms constitutes an important and challenging task in complex terrain. This is especially due to the complex interactions of the boundary layer flows in complex terrain and wind turbine wakes, which renders wake modelling in co ...

ELSEVIER SCI LTD2020

On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems

Volkan Cevher, Ali Kavis, Shaul Nadav Hallak

This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm’s convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with prob ...

2020

The electric autonomous dial-a-ride problem

Claudia Bongiovanni

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

EPFL2020

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

On the various local solutions to a two-input dynamic optimization problem

Dominique Bonvin

Solving a multi-input dynamic optimization of a batch processes is a complex problem involving interactions between input variables and constraints over time. The problem gets more difficult due to the presence of local solutions that have almost the same ...

Elsevier2016

Exploring Local Modifications for Constrained Meshes

Mark Pauly, Sofien Bouaziz, Bailin Deng, Yuliy Gennadievich Schwartzburg, Mario Moacir Deuss

Mesh editing under constraints is a challenging task with numerous applications in geometric modeling, industrial design, and architectural form finding. Recent methods support constraint-based exploration of meshes with fixed connectivity, but commonly la ...

Wiley-Blackwell2013

Crowdsourcing As A Solution To Distant Search

Christopher Tucci, Allan Afuah

We argue that under certain circumstances crowdsourcing transforms distant search into local search, improving the efficiency and effectiveness of problem solving. Under such circumstances a firm may choose to crowdsource problem solving rather than solve ...

Academy of Management2012

Container Terminal Management : Integrated Models and Large-Scale Optimization Algorithms

Ilaria Vacca

This thesis deals with models and methods for large scale optimization problems; in particular, we focus on decision problems arising in the context of seaport container terminals for the efficient management of terminal operations. Large-scale optimizatio ...

EPFL2011

A heuristic for nonlinear global optimization

Michel Bierlaire, Michaël Clément Louis Ghislain Thémans, Nicolas Zufferey

We propose a new heuristic for nonlinear global optimization combining a variable neighborhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search if ...

2010

Design of tensegrity structures using parametric analysis and stochastic search

Ian Smith, Landolf-Giosef-Anastasios Rhode-Barbarigos, Himanshu Jain

Tensegrity structures are lightweight structures composed of cables in tension and struts in compression. Since tensegrity systems exhibit geometrically nonlinear behavior, finding optimal structural designs is difficult. This paper focuses on the use of s ...

Springer Verlag2010

A heuristic for nonlinear global optimization

Michel Bierlaire, Michaël Clément Louis Ghislain Thémans, Nicolas Zufferey

We propose a new heuristic for nonlinear global optimization combining a variable neighbourhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search i ...

2008

A heuristic for nonlinear global optimization

Michel Bierlaire, Michaël Clément Louis Ghislain Thémans, Nicolas Zufferey

We propose a new heuristic for nonlinear global optimization combining a variable neighborhood search framework with a modified trust-region algorithm as local search. The proposed method presents the capability to prematurely interrupt the local search if ...

2008

Variable space search for graph coloring

Nicolas Zufferey, Matthieu Plumettaz

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1, ..., k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, ...

2008