6
$\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

$$\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?

$\endgroup$
6
  • 2
    $\begingroup$ Captain Obvious: with no objective function you only wish to know if the intersection of halfspaces is non-empty (the witness would be your solution). $\endgroup$
    – dtldarek
    Feb 27, 2013 at 23:04
  • $\begingroup$ What does the superscript T over the 0 means? $\endgroup$ Sep 6, 2018 at 16:00
  • 2
    $\begingroup$ @MurilloHenrique -- $0$ and $x$ are vectors, $0^T x$ is the dot product of these vectors: en.wikipedia.org/wiki/Dot_product#Algebraic_definition $\endgroup$
    – fbahr
    Apr 13, 2019 at 12:20
  • 1
    $\begingroup$ @dtldarek Could you please elaborate on your comment a little more? I don't understand what you mean by "intersection of halfspaces is non-empty". A link to an example would probably help a lot. Thanks! $\endgroup$
    – Gilfoyle
    Mar 29, 2021 at 13:46
  • $\begingroup$ @Samuel Each linear constraint is equivalent to a half-space, there exists a point that satisfies all the constraints if and only if there exists a point that belongs to the intersection of all these half-spaces. $\endgroup$
    – dtldarek
    Mar 29, 2021 at 15:58

2 Answers 2

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.