The 2017 Iriomote Workshop on Parallel Tree Search and Discrete Optimization
A workshop held from May 25, 2017 until June 2, 2017 in Iriomote, Japan.


A small workshop will be held at the Nirakanai Hotel (ホテルニラカナイ小浜島) in Iriomote, Japan, from May 25, 2017 until June 2, 2017.

There will be talks by three speakers:

The workshop is part of a five-year JSPS project entitled Large scale parallelization for geometric computation with mathematical programming applications (幾何計算のための大規模並列化と数理計画法への応用). That project is summarized as follows: Most research in algorithms since the 1970s has been for single processor machines, resulting in a vast amount of sophisticated and robust software. Unfortunately most of this software profits very little when run on the now prevalent multiprocessor hardware. The redesign and reimplementation of all this software will be an extremely time consuming and expensive task. The purpose of this research is to efficiently parallelize certain algorithms without any essential change to their existing implementation. This is achieved by adding parallelization as a wrapper to the existing code. This technique will be applied to tree search algorithms used in geometric computation, discrete optimization, AI and machine learning.


  • Thursday May 25, 2017: Arrival at the Nirakanai Hotel in Iriomote.
  • Friday May 26, 2017-June 1, 2017: Workshop. We will have talks in the morning (Nirakanai conference room, 10-12am) by the main speakers, and open problem and work sessions in the afternoons (Nirakanai conference room, 2-5pm). The topics of the talks will be as follows:
    • May 26-May 28 (David Avis). Branch and bound with LP bounding.
    • May 29-May 30 (Luc Devroye). Analysis of parallel DFS and BFS search on Galton-Watson trees.
    • May 31-June 1 (William Cooke). Analysis of TSP branch and cut trees.
  • Friday, June 2, 2017: Departure of all participants.


The meeting is organized by David Avis (Graduate School of Informatics, Kyoto University, Kyoto, Japan).


All participants are responsible for their own meals. Near the workshop hotel, one can dine at Kitchen Inaba ($$) and Shima Italian En ($$). The workshop dinner is planned at Restaurant Hirugi in the port of Ishigaki at 7pm on June 1. The cost per participant will be about 4000 yen or 40 US dollars.


The workshop takes place at the Nirakanai Hotel, which is located on the island of Iriomote, Japan. Google Maps.

Iriomote can be reached by a brief boat transfer from Ishigaki Jima via the port of Uehara. From the port, there are taxis, or one can walk (ca. 35 minutes). Ishigaki has many daily flights to Osaka and Tokyo.

About Iriomote

Iriomote (西表島), like the rest of Japan, is safe. In May, the temperature is quite pleasant, ca. 25 degrees, thanks to the a cooling ocean breeze.


Participants should find their own accommodation. The Nirakanai is a luxury hotel. For cheaper options, participants might consider Villa Iriomote in Uehara, or hotels in the port of Ishigaki such as Hotel Easy China Sea.