Imamichi, Takashi, Yagiura, Mutsunori, Nagamochi, Hiroshi
The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps...
Exact Algorithms for the 2-Dimensional Strip Packing Problem with and without Rotations (2008)
Mitsutoshi Kenmochi, Takashi Imamichi, Koji Nonobe, Mutsunori Yagiura, Hiroshi Nagamochi
Abstract. We examine various strategies for exact approaches to the 2dimensional strip packing problem (2SP) with and without rotations of 90 degrees. We first develop a branch-and-bound algorithm...
Shunji Umetani, Mutsunori Yagiura, Takashi Imamichi, Shinji Imahori, Toshihide Ibaraki
guided local search based on a fast neighborhood search for the
© 2004 INFORMS An Ejection Chain Approach for the Generalized Assignment Problem (2008)
Mutsunori Yagiura, Toshihide Ibaraki, Fred Glover
informs ®
Mutsunori Yagiura, Shinji Iwasaki, Toshihide Ibaraki, Fred Glover
Abstract: We propose a metaheuristic algorithm for the multi-resource generalized assignment problem (MRGAP). MRGAP is a generalization of the generalized assignment problem, which is one of the...
A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns (2008)
HARAGUCHI, Kazuya, YAGIURA, Mutsunori, BOROS, Endre, IBARAKI, Toshihide
We consider a data set in which each example is an n-dimensional Boolean vector labeled as true or false. A pattern is a co-occurrence of a particular value combination of a given subset of the...
RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM (2007)
Umetani, Shunji, Yagiura, Mutsunori, 柳浦, 睦憲
The set covering problem (SCP) is one of representative combinatorial optimization problems, which has many practical applications. The continuous development of mathematical programming has derived...
Cutting Stock Problem, Shunji Umetani, Mutsunori Yagiura, Toshihide Ibaraki
One dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which has many applications in, e.g., steel, paper and fiber industries. To define an...
Mutsunori Yagiura, Masahiro Kishida, Toshihide Ibaraki
Abstract: The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search...
+ Web Service Group, NTT Data Corporation (2007)
Mutsunori Yagiura, Shinji Iwasaki, Toshihide Ibaraki
We propose a metaheuristic algorithm for the multi-resource generalized assignment problem (MRGAP) [5]. MRGAP is a further generalization of the generalized assignment problem (GAP) [8, 10, 11],...
An Index for the Data Size to Extract Decomposable Structures in LAD (2007)
Hirotaka Oho, Mutsunori Yagiura, Toshihide Ibaraki
Abstract. Logical analysis of data (LAD) is one of the methodologies for extracting knowledge as a Boolean function f from a given pair of data sets (T,F) on attributes set $ of size n, in which T...
Mutsunori Yagiura, Masahiro Kishida, Toshihide Ibaraki
Abstract: The set covering problem (SCP) asks to choose a minimum cost family of subsets from given n subsets, which together covers the entire ground set. In this paper, we propose a local search...
A Very Large-Scale Neighborhood Search Algorithm (2007)
Mutsunori Yagiura, Shinji Iwasaki, Toshihide Ibaraki, Fred Glover
We propose a metaheuristic algorithm for the multi-resource generalized assignment problem (MRGAP). MRGAP is a generalization of the generalized assignment problem, which is one of the representative...
Hybrid Metaheuristics for Packing Problems (2007)
Toshihide Ibaraki, Shinji Imahori, Mutsunori Yagiura, Toshihide Ibaraki, Shinji Imahori, Mutsunori Yagiura
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
A path relinking approach for the generalized assignment problem (2002)
Mutsunori Yagiura, Toshihide Ibaraki, Fred Glover
The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine...
Local Search Heuristics for the Rectangle Packing (2001)
Problem With General, Shinji Imahori, Mutsunori Yagiura, Toshihide Ibaraki
this paper the rectangle packing problem in which each rectangle has a spatial cost (RPGSC). The problem is to pack a given set of n rectangles without overlap so that the maximum cost of the...
On metaheuristic algorithms for combinatorial optimization problems (2001)
Mutsunori Yagiura, Toshihide Ibaraki
Abstract: Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithm,...
On metaheuristic algorithms for combinatorial optimization problems (2001)
Mutsunori Yagiura, Mutsunori Yagiura
on
Finding Small Sets of Essential Attributes in Binary Data (2000)
Endre Boros, Endre Boros, Takashi Horiyama, Takashi Horiyama, Toshihide Ibaraki, Toshihide Ibaraki, ...
.We consider the problem of nding support sets (i.e., sets of essential attributes) in a given data set, which consists of n-dimensional binary vectors of positive examples and negative examples. A...
Fast Algorithms to Enumerate All Common Intervals of Two Permutations (2000)
Takeaki Uno, Mutsunori Yagiura
Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a common interval. Some genetic algorithms based on such common...
Finding essential attributes from binary data (2000)
Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura
We consider data sets that consist of n-dimensional binary vectors representing positive and negative examples for some (possibly unknown) phenomenon. A subset S of the attributes (or variables) of...
An ejection chain approach for the generalized assignment problem (1999)
Mutsunori Yagiura, Toshihide Ibaraki, Fred Glover
We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an...
A Variable Depth Search Algorithm for the Generalized Assignment Problem (1999)
Mutsunori Yagiura, Takashi Yamaguchi, Toshihide Ibaraki
: A variable depth search procedure (abbreviated as VDS) is a generalization of the local search method, which was rst successfully applied by Lin and Kernighan to the traveling salesman problem and...
Mutsunori Yagiura, Toshihide Ibaraki
Abstract. For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most eective approaches. Most of the local search algorithms are based on the 1- ip neighborhood,...
Genetic and Local Search Algorithms as Robust and Simple Optimization Tools (1996)
Mutsunori Yagiura, Toshihide Ibaraki
: One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various genetic...
The Use of Dynamic Programming in Genetic Algorithms for Permutation Problems (1996)
Mutsunori Yagiura, Toshihide Ibaraki
To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were...
Metaheuristics as Robust and Simple Optimization Tools (1996)
Mutsunori Yagiura, Toshihide Ibaraki
One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various metaheuristics,...
Exact algorithms for the two-dimensional strip packing problem with and without rotations
Kenmochi, Mitsutoshi, Imamichi, Takashi, Nonobe, Koji, Yagiura, Mutsunori, Nagamochi, Hiroshi
We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP,...