4
$\begingroup$

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

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

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?

$\endgroup$
1
$\begingroup$
  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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.