Abstract : Combinatorial optimization problems aim to compute optimal solutions under a series of constraints, where the set of feasible solutions is discrete, such as scheduling and routing problems. It involves thousands of real-world problems. This minisymposium will focus on mathematical modeling and combinatorial optimization. We have eight junior and senior researchers giving their latest research results on algorithm design, modeling of real-world problems and simulation. The purpose of this minisymposium is to discuss new ideas and challenging problems, as well as to explore new research topics.
[02230] Sports Scheduling: Number of Trips in the Traveling Tournament Problem
Format : Talk at Waseda University
Author(s) :
Takaki Ono (Chuo University)
Shinji Imahori (Chuo University)
Abstract : This talk deals with the traveling tournament problem, which is a well-known benchmark problem in the field of sports scheduling. We propose a new technique to improve the efficiency of an existing algorithm for the problem. We also design a new method to improve the quality of solutions. Our method first solves an integer programming problem to compute a round-robin tournament, and constructs a double round-robin tournament with smaller number of trips.
[04421] Efficient allocation of demand to facilities on road networks
Format : Talk at Waseda University
Author(s) :
Ken-ichi Tanaka (Keio University)
Mutsunori Yagiura (Nagoya University)
Abstract : We focus on road networks in which some facilities exist and demand for deliveries arises along the edges of the network. We consider the problem of assigning a subset of edges to each facility so that the total facility-demand delivery distances are minimized with the constraint that each facility addresses almost the same amount of demand. We propose an approach to obtain simple and geographically compact service areas by iteratively solving integer optimization problems.
[01600] Optimal UAV Flight Path Planning for Herding Sheep
Format : Talk at Waseda University
Author(s) :
I-Lin Wang (Professor)
Ying-Ting Lin (Ph.D. student)
Abstract : We will first introduce how literature solves the shepherding problem by autonomous agents. All the previous research designed heuristic algorithms to collect the sheep when they are too dispersed and then drive them to the destination after aggregating them. We, on the other hand, propose an innovative framework based on graph theory and integer programming models. Our approaches have a significant performance improvement and provide a new viewpoint on how this problem can be solved.
[02992] Formulations and algorithms for a square independent packing problem
Format : Talk at Waseda University
Author(s) :
Wei Wu (Shizuoka University)
Hiroki Numaguchi (Tokyo University of Science)
Jotaro Kuno (Nagoya University)
Yannan Hu (Tokyo University of Science)
Vitor Mitsuo Fukushige Hama (Nagoya University)
Mutsunori Yagiura (Nagoya University)
Abstract : Given a set of squares and a strip with a fixed width, we consider a square independent packing problem (SIPP) that minimizes the strip height such that all squares are packed into cells by setting vertical and horizontal dividers that pass through the entire strip. We show that the SIPP is NP-hard. To solve the SIPP, we design three mathematical formulations based on different solution representations, and then we propose a fully polynomial-time approximation scheme.
[02859] A core selection method for the robust traveling salesman problem
Format : Talk at Waseda University
Author(s) :
Kazuki Hasegawa (Shizuoka University)
Wei Wu (Shizuoka University)
Mutsunori Yagiura (Nagoya University)
Abstract : We consider the robust traveling salesman problem with interval costs under a min–max regret criterion. We first show that the iterated dual substitution method is applicable for solving this problem, and we examine 18 implementations based on different cut generation rules and mathematical models of the classical traveling salesman problem. Then, we propose a new heuristic approach: core selection method. The core selection method achieved state-of-the-art results on all benchmark instances.
[02909] Algorithms for two-machine job-shop scheduling problem with one joint job
Format : Talk at Waseda University
Author(s) :
Hiroki Numaguchi (Tokyo University of Science)
Wei Wu (Shizuoka University)
Yannan Hu (Tokyo University of Science)
Abstract : We introduce a two-machine job-shop scheduling problem with one joint job where a joint job is defined as a job whose operations are to be processed by different machines. We prove that this problem is strongly NP-hard and propose a polynomial-time algorithm based on dynamic programming when the number of jobs is given as a fixed number. We further improve time complexity using various techniques, including the two-pointers method.
[04538] A New Multivariate Decision Tree Based on Mixed Integer Linear Programming
Format : Talk at Waseda University
Author(s) :
Ryo Kurosu (University of Kyoto)
Kazuya Haraguchi (University of Kyoto)
Abstract : We study a novel framework of inferring molecule structures that are expected to have desired properties (e.g., high boiling point, low solubility), exploiting machine learning and operations research, where accurate prediction tools are indispensable. In this paper, we propose a new classification decision tree algorithm that builds a multivariate decision tree (i.e., node split is done by hyperplane) based on mixed integer linear programming. Our algorithm is a generalization of conventional ones in the sense that their decision trees are univariate. We describe experimental results on how accurate decision trees are built by our algorithm and by conventional ones, using data sets from cheminformatics.
[04561] A Linear Delay Algorithm for Enumeration of $2$-Edge/Vertex-connected Induced Subgraphs
Format : Talk at Waseda University
Author(s) :
Takumi Tada (Graduate School of Informatics, Kyoto University, Japan)
Kazuya Haraguchi (Graduate School of Informatics, Kyoto University, Japan)
Abstract : In this paper, we present the first linear delay algorithms to enumerate all 2-edge-connected induced subgraphs and to enumerate all 2-vertex-connected induced subgraphs for a given simple undirected graph. We treat these subgraph enumeration problems in a more general framework based on set systems. For an element set $V$, $(V,{\mathcal C}\subseteq 2^V)$ is called a {\em set system}, where we call $C\in{\mathcal C}$ a {\em component}. A nonempty subset $Y\subseteq C$ is a {\em removable set of $C$} if $C\setminus Y$ is a component and $Y$ is a {\em minimal removable set} ({\em MRS}) {\em of $C$} if it is a removable set and no proper nonempty subset $Z\subsetneq Y$ is a removable set of $C$. We say that a set system has {\em subset-disjoint} ({\em SD}) property if, for every two components $C,C'\in{\mathcal C}$ with $C'\subsetneq C$, every MRS $Y$ of $C$ satisfies either $Y\subseteq C'$ or $Y\cap C'=\emptyset$. We assume that a set system with SD property is implicitly given by an oracle that returns an MRS of a component which is given as a query. We provide an algorithm that, given a component $C$, enumerates all components that are subsets of $C$ in linear time/space with respect to $|V|$ and oracle running time/space. We then show that, given a simple undirected graph $G$, the pair of the vertex set $V=V(G)$ and the family of vertex subsets that induce 2-edge-connected (or 2-vertex-connected) subgraphs of $G$ has SD property, where an MRS in a 2-edge-connected (or 2-vertex-connected) induced subgraph corresponds to either an ear or a single vertex with degree greater than two.
