Application of CMSA in the Presence of Non-binary Variables

Up to this point, the applications of CMSA discussed in this book, as well as those found in the related literature, have focused on addressing combinatorial optimization problems that can be expressed through binary integer linear programming (ILP) formulations. Such problems represent an ideal scenario for CMSA, as sub-instances can be easily defined by fixing specific decision variables to certain values or excluding them altogether from the models. However, when confronted with a problem expressed through a more general ILP that incorporates discrete decision variables with non-binary domains, a notable challenge emerges. Unlike constraint programming solvers, for example, ILP solvers cannot handle non-contiguous domains, making it impossible to simply eliminate certain values from these domains. In this chapter, we present an illustration of CMSA applied to a combinatorial optimization problem naturally formulated as a non-binary ILP. Specifically, we make use of the Bounded Knapsack Problem with Conflicts.