  Emerging quantum computing technologies, such as Noisy Intermediate-Scale
Quantum (NISQ) devices, offer potential advancements in solving mathematical
optimization problems. However, limitations in qubit availability, noise, and
errors pose challenges for practical implementation. In this study, we examine
two decomposition methods for Mixed-Integer Linear Programming (MILP) designed
to reduce the original problem size and utilize available NISQ devices more
efficiently. We concentrate on breaking down the original problem into smaller
subproblems, which are then solved iteratively using a combined
quantum-classical hardware approach. We conduct a detailed analysis for the
decomposition of MILP with Benders and Dantzig-Wolfe methods. In our analysis,
we show that the number of qubits required to solve Benders is exponentially
large in the worst-case, while remains constant for Dantzig-Wolfe.
Additionally, we leverage Dantzig-Wolfe decomposition on the use-case of
certifying the robustness of ReLU networks. Our experimental results
demonstrate that this approach can save up to 90\% of qubits compared to
existing methods on quantum annealing and gate-based quantum computers.
