In this study, we explore how the domain of objective function values for challenging integer programs can be reduced and whether such a reduction can improve the solution process. Our work is motivated by binary search, a technique that efficiently narrows a search space by repeatedly halving it through feasibility checks. Building on this idea, we first propose a method that combines binary search with branch-and-bound techniques by encoding objective values in terms of bits, which we call the Bitwise Branch-and-Bound method. The method attempts to determine the value of each bit, from the most significant bit to the least significant one, progressively tightening the objective value bounds. When these bounds converge to a single value, the optimal solution is identified directly. Otherwise, the method returns a set of disjoint ranges guaranteed to contain the optimal value, effectively reducing the objective-value domain. To exploit this reduction, we introduce a reformulation, referred to as the Domain-Reduced Reformulation, which passes the disjoint ranges to an integer programming solver. We apply the proposed framework, including both the Bitwise Branch-and-Bound method and the Domain-Reduced Reformulation, to two classes of challenging integer programs: the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The proposed approach is evaluated on standard benchmark instances and compared against the direct use of an integer programming solver with lazy constraint callbacks. While the standard solver performs better on easy-to-medium instances, the proposed method provides significant improvements on more challenging instances in terms of both computational time and optimality gap.