I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize.
I've been using lp_solve to solve this problem and it works well — I simply define my objective function to be
$$\begin{array}{ll} \text{maximize} & {\bf 0}^T {\bf x}\end{array}$$
However, this seems kind of silly and I keep wondering if there is a better way.
Is there a name for linear programming problems with no objective function? If I don't have an objective function is there some technique more efficient than linear programming (in particular, branch and bound) that I should be using?
Best Answer
Finding an initial feasible solution to an LP can be achieved using phase one of the "two phase method" (phase two is the simplex method, a famous algorithm for solving linear programs). So, for lack of a better name, I would call this a "phase 1" problem.
While there ARE instances of integer programs that CAN be solved with LP (e.g. when the values of the linear program parameters $(A,b,c)$ are integer and the $A$ matrix is totally unimodular), in general binary integer programs cannot be solved with linear programming.
Lp_solve uses branch and bound to handle the integer variables in your problem. Your post indicates it works well, so I wouldn't recommend doing anything differently. However, if you have less success with larger problems, you have options. One of the (many) potential reasons there would be trouble for large-scale is the weak LP relaxations from the branch-and-bound subproblems. These can be tightened using cutting plane methods. However, rather than implementing a new technique, I would suggest trying a different solver (commercial solvers such as Gurobi or CPLEX are fantastic).