## Contributed Session Wed.1.H 3012

#### Wednesday, 10:30 - 12:00 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Heuristics I

**Chair: Shunji Umetani**

**Wednesday, 10:30 - 10:55 h, Room: H 3012, Talk 1**

**Toppur Natarajan Badri**

A divide-and-bridge heuristic for Steiner minimal trees on the Euclidean plane

**Abstract:**

This paper describes the construction of Steiner minimal trees on the Euclidean plane using a divide-and-bridge heuristic. A lexicographically sorted set of terminal sites is divided into subsets. These subsets with three, four or five vertices in each set are created using recursive division by two. The optimal Steiner tree length and topology for each subset are calculated using an exponential time exact algorithm.

Any two neighboring trees calculated above, can be bridged by the edge of shortest length. Because of the repeated division of the given set into halves, an outlying terminal of a subset may better suit the total connectivity if it is included in the neighboring subset. We start with a feasible division that may not be optimal, and then look for the optimal division by moving the boundary between two subsets, if it is promising. Split operations may be required at the terminals of the bridge edge, to obtain the minimal tree for the merged set. After every bridge operation or split operation, the optimal coordinates are calculated by an algorithm, that works in *O(N)* time since the topology is known.

**Wednesday, 11:30 - 11:55 h, Room: H 3012, Talk 3**

**Shunji Umetani**

A heuristic algorithm for the set multicover problem with generalized upper bound constraints

**Coauthors: Masanao Arakawa, Mutsunori Yagiura**

**Abstract:**

We consider an extension of the set covering problem (SCP) introducing (i) multicover and (ii) generalized upper bound (GUB) constraints.

For the conventional SCP, the pricing method has been introduced to reduce the number of variables, and several efficient heuristic algorithms based on this idea have been developed to solve very large-scale instances.

However, GUB constraints often make the pricing method less effective, because they prevent solutions from having highly evaluated variables simultaneously.

To overcome this, we propose a heuristic algorithm to reduce the size of problem instances that modifies the evaluation scheme of variables taking account of GUB constraints.

We also develop an efficient implementation of a local search algorithm with the 2-flip neighborhood that reduces the number of candidates in the neighborhood without sacrificing the solution quality.

According to computational comparison on benchmark instances with the latest mixed integer programming solver, our algorithm performs quite effectively for various types of instances, especially for very large-scale instances.