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?
Thank you in advance.
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.