@article{ART002032869},
author={Junha Hwang},
title={An Integer Programming-based Local Search for the Set Partitioning Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={9},
pages={21-29}
TY - JOUR
AU - Junha Hwang
TI - An Integer Programming-based Local Search for the Set Partitioning Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 9
PB - The Korean Society Of Computer And Information
SP - 21
EP - 29
SN - 1598-849X
AB - The set partitioning problem is a well-known NP-hard combinatorial optimization problem, and it is formulated as an integer programming model. This paper proposes an Integer Programming-based Local Search for solving the set partitioning problem. The key point is to solve the set partitioning problem as the set covering problem. First, an initial solution is generated by a simple heuristic for the set covering problem, and then the solution is set as the current solution. Next, the following process is repeated. The original set covering problem is reduced based on the current solution, and the reduced problem is solved by Integer Programming which includes a specific element in the objective function to derive the solution for the set partitioning problem. Experimental results on a set of OR-Library instances show that the proposed algorithm outperforms pure integer programming as well as the existing heuristic algorithms both in solution quality and time.
KW - Set partitioning problem;Set covering problem;Integer programming-based local search
DO -
UR -
ER -
Junha Hwang. (2015). An Integer Programming-based Local Search for the Set Partitioning Problem. Journal of The Korea Society of Computer and Information, 20(9), 21-29.
Junha Hwang. 2015, "An Integer Programming-based Local Search for the Set Partitioning Problem", Journal of The Korea Society of Computer and Information, vol.20, no.9 pp.21-29.
Junha Hwang "An Integer Programming-based Local Search for the Set Partitioning Problem" Journal of The Korea Society of Computer and Information 20.9 pp.21-29 (2015) : 21.
Junha Hwang. An Integer Programming-based Local Search for the Set Partitioning Problem. 2015; 20(9), 21-29.
Junha Hwang. "An Integer Programming-based Local Search for the Set Partitioning Problem" Journal of The Korea Society of Computer and Information 20, no.9 (2015) : 21-29.
Junha Hwang. An Integer Programming-based Local Search for the Set Partitioning Problem. Journal of The Korea Society of Computer and Information, 20(9), 21-29.
Junha Hwang. An Integer Programming-based Local Search for the Set Partitioning Problem. Journal of The Korea Society of Computer and Information. 2015; 20(9) 21-29.
Junha Hwang. An Integer Programming-based Local Search for the Set Partitioning Problem. 2015; 20(9), 21-29.
Junha Hwang. "An Integer Programming-based Local Search for the Set Partitioning Problem" Journal of The Korea Society of Computer and Information 20, no.9 (2015) : 21-29.