# Reconfiguration to find other solutions of a Binary Linear Program (NOT ILP)

Assuming we are to optimize 0-1 problem. If we've found the first solutions where multiple solutions might exists. How do we reconfigure the system (maybe through unimodular operations) inorder to find other Binary solutions.
For example take $$\min f(x)$$ Subject to $$x^\top A = b$$ where $$x_i \in \{0,1\},\ b_i \in \{0,1\}$$ $$x$$ is a vector and $$x_i$$ is an element in the vector same for $$b$$ and $$b_i$$ respectively.
given the first solution $$y$$.

Can it be done in polynomial time? If it can be done what might be the complexity? or is it NP Hard. if it can't be done is there a way to check if the system has other feasible binary solutions? and what might be the complexity of the algorithm?

A generic approach to find multiple feasible binary solutions is to add a no-good constraint that cuts off a given solution $$\hat{x}$$: $$\sum_{j:\hat{x}_j=0} x_j + \sum_{j:\hat{x}_j=1} (1 - x_j) \ge 1$$ Solve, introduce an additional no-good cut, and repeat until the problem becomes infeasible. There can be exponentially many feasible solutions, so there is no hope for polynomial time.
• do you mean that there is hope for polynomial time algorithm if only a finite group of solution is to be found? what about checking if there can be a solution other than $y$ Commented Jul 23, 2022 at 17:53
• No, still no hope without severe restrictions on $A$ and $b$. Commented Jul 23, 2022 at 18:02