4
$\begingroup$

I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.

Let us look at two examples to illustrate my problem. On the one hand, the knapsack problem is an NP-hard problem which is defined as follows:

$$ \begin{align*}\tag{$\mathit{P}_1$} & {\underset{\mathbf{ x }}{\text{maximize}}} & & \sum_{j=1}^nv_jx_j\\[3pt] & \text{subject to} & & \sum_{j=1}^{n} w_jx_j \leqslant\mathit{W},\\[3pt] & & & x_j \in\{0, 1\}, \forall\, j. \end{align*} $$ However, finding a feasible solution to the knapsack problem is not NP-hard. In other words, find $x_j\in\{0, 1\}$ for $j=1,\ldots, n$ such that $\sum_{j=1}^{n} w_jx_j \leqslant\mathit{W}$ is easy.

On the other hand, the variable-sized bin packing problem is also NP-hard and is given by the following 0-1 integer program:

$$ \begin{align*}\tag{$\mathit{P}_2$} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum_{j=1}^ny_j\\[3pt] & \text{subject to} & & \sum_{i=1}^{m} a_ix_{ij} \leqslant\mathit{V}_jy_j,\forall\, j\\[3pt] & & & \sum_{j=1}^n x_{ij}=1, \forall\, i.\\[3pt] & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i, j. \end{align*} $$ However, finding a binary variables $x_{ij}$ for $i=1\ldots,m$ and $j=1,\ldots,n$ seems to be as hard as finding a solution to the bin packing problem.

In fact, if I apply the first-fit algorithm to the following instance of bin packing: two bins with capacities $V_1=3$ and $V_2=4$, respectively, and three items with values $a_1=2$, $a_2=2$ and $a_3=3$. The first-fit algorithm (if it processes the items in the order $a_1$, $a_2$ and $a_3$ will put item 1 into bin 1, item 2 into bin 2 and there is no bin left (i.e., $n=2$). Hence, the first-fit algorithm should output error or something since it cannot assign all items to the $n$ bins. Clearly, the optimal assignment can be items 1 and 2 into bin 2 and item 3 into bin 1. How to solve this issue with the greedy first-fit algorithm?

In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors? For example, for the bin packing problem, all the papers I found are not interested in finding feasibility but they are trying to the solve the problem when it is feasible. In many practical cases we cannot pack all the items in $n$ bins using our greedy approaches (even though the optimal algorithm can).

Any suggestions where to find solutions to feasibility of 0-1 integer programs?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems. But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time. So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:

[Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.] How to solve this issue with the greedy first-fit algorithm?

You can't. The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't). Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either. It's no surprise that it fails to find a feasible solution to a NP-hard problem. And there is (most likely) no way to fix it, while still having an efficient running time.

In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?

In general, there may be no way.

Any suggestions where to find solutions to feasibility of 0-1 integer programs?

There's lots of literature on methods for solving integer linear programming (ILP). None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution is NP-hard), though some of them might work well enough on some problems that you run into in practice. Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the greedy approximation algorithm First-Fit fails to give an answer when an answer actually exists? In the example I gave, First-Fit cannot assign items into two bins, therefore, it will not give any solution as I only have two bins. In general, I understand that First-Fit will produce a solution that is at most $c$ times the optimal but in this case it does not give this value. Why? $\endgroup$
    – Ribz
    Commented Nov 8, 2016 at 22:52
  • $\begingroup$ A constant approximation algorithm should always give a solution that is bounded above by the optimal times a constant, say. That is, for any instance of the problem, $|\mathit{ALG}|\leqslant c |\mathit{OPT}|$, where $|\mathit{ALG}|$ (resp. $|\mathit{OPT}|$) is the value of the algorithm $\mathit{ALG}$ (resp. the optimal algorithm $\mathit{OPT}$). If $\mathit{ALG}$ fails to find a feasible solution for some instance, should we ignore this particular instance? $\endgroup$
    – Ribz
    Commented Nov 8, 2016 at 22:59
1
$\begingroup$

Did you check Lenstra

http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1981d/art.pdf

I understand from that report that the feasability problem with a fixed number of variables can be done in polynomial time

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The number of variables doesn't seem to be fixed in the examples from the question. $\endgroup$
    – adrianN
    Commented Oct 18, 2017 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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