Information-Assisted Dynamic Programming for a Class of Constrained Combinatorial Problems

Abstract

The constrained discrete optimization (CDO) problems pose an immense challenge to solve with provable accuracy and computational efficiency. Dynamic programming (DP) is an elegant technique that is used to solve a class of such problems with linear constraints that follow a particular structure, namely Bellman’s principle of optimality (BPO). Unfortunately, many of the CDO problems do not fall into this category. This work focuses on solving a class of CDO problems, which we call problem class $H$ , that do not satisfy BPO if the constraint functions are considered. There are no conditions placed on the constraint functions of $H$ . However, the objective function alone satisfies the BPO. Such problems are ubiquitous in wireless communication, signal processing, and machine learning. These problems are, in general, NP-Hard. This paper attempts to unify this class of problems to be solvable using the DP framework. Using the theory of multi-objective optimization and assisted by an information-theoretic measure, we establish provable near-optimality guarantees with reduced computational complexity. We describe two algorithms to solve $H$ . We support our claims by solving the power-constrained analog-to-digital converter bit allocation (BA) problem in massive Multiple-Input Multiple-Output (MaMIMO) receivers. The optimal BA thus obtained ensures the maximum energy efficiency of the MaMIMO receiver.

Keywords

• Bellman’s optimality principle
• dynamic programming
• information-to-go
• Kullback-Leibler divergence
• multi-objective optimization
• Pareto optimal solution