Counterfactual explanations (CEs) offer a human-understandable way to explain decisions by identifying specific changes to the input parameters of a base or present model that would lead to a desired change in its outcome. For optimization models, CEs have primarily been studied in limited contexts, such as linear optimization problems with continuous decision variables or binary optimization problems where only the objective function can be altered. However, little research has been done on CEs for general integer optimization problems. In this work, we address this gap by proving that constructing a CE is $\Sigma_2^p$-complete even for binary integer programs with just a single mutable constraint. Additionally, we propose solution algorithms for several cases: (i) mutable objective parameters, (ii) a single mutable constraint, (iii) mutable right-hand-side, and (iv) all input parameters can be modified. We evaluate our approach using classical knapsack problem instances, focusing on cases with mutable constraint parameters. Our results show that our methods are capable of finding optimal CEs for small instances involving up to 40 items within a few hours.