Efficient partition of integer optimization problems with one-hot encoding

Abstract Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a l...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Shuntaro Okada, Masayuki Ohzeki, Shinichiro Taguchi
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2019
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/d937272683344367bdc7d0e862a87aa6
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d937272683344367bdc7d0e862a87aa6
record_format	dspace
spelling	oai:doaj.org-article:d937272683344367bdc7d0e862a87aa62021-12-02T15:08:09ZEfficient partition of integer optimization problems with one-hot encoding10.1038/s41598-019-49539-62045-2322https://doaj.org/article/d937272683344367bdc7d0e862a87aa62019-09-01T00:00:00Zhttps://doi.org/10.1038/s41598-019-49539-6https://doaj.org/toc/2045-2322Abstract Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables. However, the cost functions of several practical problems are defined by a large number of integer variables. To solve these problems using the quantum annealer, integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably larger than that of the original integer problem and is dominated by infeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required. In this study, we propose two partitioning methods and demonstrate that they result in improved solutions.Shuntaro OkadaMasayuki OhzekiShinichiro TaguchiNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 9, Iss 1, Pp 1-12 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Shuntaro Okada Masayuki Ohzeki Shinichiro Taguchi Efficient partition of integer optimization problems with one-hot encoding
description	Abstract Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables. However, the cost functions of several practical problems are defined by a large number of integer variables. To solve these problems using the quantum annealer, integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably larger than that of the original integer problem and is dominated by infeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required. In this study, we propose two partitioning methods and demonstrate that they result in improved solutions.
format	article
author	Shuntaro Okada Masayuki Ohzeki Shinichiro Taguchi
author_facet	Shuntaro Okada Masayuki Ohzeki Shinichiro Taguchi
author_sort	Shuntaro Okada
title	Efficient partition of integer optimization problems with one-hot encoding
title_short	Efficient partition of integer optimization problems with one-hot encoding
title_full	Efficient partition of integer optimization problems with one-hot encoding
title_fullStr	Efficient partition of integer optimization problems with one-hot encoding
title_full_unstemmed	Efficient partition of integer optimization problems with one-hot encoding
title_sort	efficient partition of integer optimization problems with one-hot encoding
publisher	Nature Portfolio
publishDate	2019
url	https://doaj.org/article/d937272683344367bdc7d0e862a87aa6
work_keys_str_mv	AT shuntarookada efficientpartitionofintegeroptimizationproblemswithonehotencoding AT masayukiohzeki efficientpartitionofintegeroptimizationproblemswithonehotencoding AT shinichirotaguchi efficientpartitionofintegeroptimizationproblemswithonehotencoding
_version_	1718388284953985024

Efficient partition of integer optimization problems with one-hot encoding

Ejemplares similares