Issue: 2026/Vol.36/No.4, Pages
ENTROPY-BASED REDUCTION OPERATOR FOR HEURISTIC BINARY OPTIMIZATION
Nedjmeddine Kantour
, Khadidja Chaabane , Sadek Bouroubi
This is not yet the definitive version of the paper. This version will undergo additional copyediting, typesetting and review before it is published in its final form, but we are providing this version to give early visibility of the article.
Cite as: N. Kantour, K. Chaabane, S. Bouroubi. Entropy-based reduction operator for heuristic binary optimization. Operations Research and Decisions 2026: 36(4). DOI 10.37190/ord/231140
Abstract
In this paper, we propose a reduction operator addressing discrete optimization problems, more precisely, for optimization problems with binary represented decisions. This operator may be integrated within various metaheuristics in order to reduce the dimension of the target problem. This is, by performing an iterative supervision over the browsed admissible space throughout the search process. We thus use the information entropy concept to measure the current uncertainty towards decision variables current values provided by an iterative heuristic search algorithm. Hence, it allows to explore the decision space more efficiently. Furthermore, we present two frameworks as effective applications of this operator: a pre-process for a hybrid approach and an interactive heuristic approach. Finally, we use the Knapsack Problem (KP) as a test problem, where we assess the impact of the proposed reduction operator over two classical search algorithms: Local Search (LS) and Genetic Algorithm (GA). More precisely, on their efficiency and the quality of the produced solutions. We further compare it against established variable-fixing approaches from the literature, on both the Knapsack Problem and standard Quadratic Unconstrained Binary Optimization (QUBO) benchmark instances. The obtained results indicate that the proposed reduction compares favorably with these approaches, and that it generalizes across constrained and unconstrained binary optimization problems.
Keywords: binary Optimization, heuristic algorithms, search space reduction, information entropy, knapsack problem, quadratic unconstrained binary optimization
Received: 19 April 2026 Accepted: 15 August 2026
Published online: 16 August 2026