Linear programming problem with no objective function

1. 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.

2. 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).

Suppose you have a (bounded) linear programming problem:

$\mathrm{maximize }\,{\bf c}^T x$

$s. t. \mathrm{A}\bf{x} \ge b$

Then you can determine a bound on the optimal solution, e.g. $\mathrm{maximize }\,{\bf c}^T x > n$ by constructing the following LP:

$\mathrm{maximize }\,{\bf 0}^T {\bf x}$

$s. t. \mathrm{A}\bf{x} \ge b$, ${\bf c}^T {\bf x} \geq n$

That LP will be feasible iff the optimal solution has at least value $n$, so you can find the true maximum of the objective function through binary search in a number of steps proportional to the logarithm of its value. So getting any feasible point can't be much easier than finding the optimum, or you could use it to make an actual quick LP solver too.

For binary integer programming in particular, there's a reduction from satisfiability to determining if a binary integer program is feasible. So checking if a BIP is feasible is still NP-complete.

That said, it's possible to find feasible solutions to some LPs relatively quickly. E.g.

$\mathrm{maximize }\,{\bf 0}^T {\bf x}$

$s. t. {\bf b}^T {\bf x} \ge d$, ${\bf x} \geq 0$

has feasible points iff the optimum of

$\mathrm{maximize }\,{\bf b}^T {\bf x}$

$s. t. {\bf x} \geq 0$

is greater than $d$, and this LP is generally unbounded if at least one element in $\bf b$ is greater than zero, otherwise the optimum is 0.