This questions is geared toward Operations Research.
I have a Mixed integer Linear Program model. My integer variables are all binary. In the model, if we fix a set of complicating binary variables (not all binary variables), my problem can be decomposed into several smaller sub-problems. Each sub-problem itself is a MIP. However, I can solve each sub-problem optimally and efficeintly although technically each sub-problem is still NP-hard. All sub-problems have the same structure.
Is there any efficient technique to tackle this sort of optimization problems. I'm aware of Bender's decomposition and Logic Based Bender's decomposition.
Thanks for your comment.
"Efficient" tends to be hit and miss. It is possible to use a variant of Benders (different, I believe, from logic-based Benders). It's suitable even when the subproblems are not themselves MIPs, but convergence speed is anybody's guess.
Let's say that $\hat{x}$ is a candidate (binary) solution to the master problem (which I will assume is minimization), and let $\hat{z}_j$ be the corresponding value of $z_j$, the surrogate variable in the master problem objective function for the objective contribution of subproblem $j$. I'm going to assume for simplicity that $z_j \ge 0$. Let $O=\{i:\hat{x}_i = 1\}$ and $Z=\{i:\hat{x}_i = 0\}$.
Plug $\hat{x}$ into subproblem $j$ and solve. If subproblem $j$ is infeasible, the Benders feasibility cut is what's called a "no-good" cut:$$\sum_{i\in Z} x_i + \sum_{i \in O} (1-x_i) \ge 1.$$This cuts off $\hat{x}$ but no other solutions, so it's a rather weak cut.
If subproblem $j$ is feasible, let $w$ be its optimal objective value. If $w = \hat{z}_j$, the solution $\hat{x}$ is acceptable (at least as far as this subproblem is concerned). If $w > \hat{z}_j$, you generate a Benders optimality cut of the form$$z_j \ge w\left( 1 - \sum_{i \in Z} x_i - \sum_{i \in O} (1-x_i) \right).$$This says that $x=\hat{x} \implies z_j\ge w$, and says nothing about $z_j$ when $x \neq \hat{x}$. So, again, it's a weak cut.
Although I have no personal experience with what I'm about to suggest, I think that for some problems another plausible approach is to use constraint programming on the master problem (with surrogate objective functions) and either backtrack when a subproblem is infeasible or add the implication $x=\hat{x} \implies z_j\ge w$ when the subproblem is feasible.