Linear programming vs. Integer programming

Question

I was trying to solve a problem where I want to choose which items to choose where each item has a number $b_i$ associated with it and a reward $r_i$ associated with it. I need to choose items that maximize my reward but the sum of the $b_i$'s need to be less than a MAX. I wanted to use linear programming (let me know if this is not the correct route).

I came up with an objective function and constraints but an additional constraint is needed to make sure the choice of an item $x_i$ was a binary integer $(0,1)$. But I read that integer programming is not efficient as linear programming.

This example is used to show the efficiency of assigning 70 jobs to 70 men, which requires finding a value of 0 or 1 for each pairing of man and job. Why is this efficient- is this different from my program? How can I know whether or not my program will be efficient like this integer program when integer programs are supposed to be NP-hard?

EDIT: My question is: To settle an account, I will deposit the user’s entire balance to their bank account. I can only settle up to S dollars at a time. For each account I settle, I receive a rebate which is a fixed dollar amount. How can I maximize the rebate while making sure I don't settle more than S dollars? For each account, I'm given the balance and the rebate amount. There may be many accounts (about 100 I think).

EDIT2

Here's an example:

MAX = 50

User1: balance = 15, rebate = 10

User2: balance = 25, rebate = 15

User3: balance = 40, rebate = 20

In this case, I would choose User1 and User2 to maximize rebate without having a balance greater than MAX. My rebate would be 10+15=25 and the balance would be 15+25=40.

The way I was trying to solve this was by using linear programming but now I'm not sure if that's guaranteed to be efficient in my case (there might be 100 or so users).

This is what my linear programming objective function was:

f(x1, x2, ... xn) = r1x1+r2x2+...+rn*xn

These were my constraints:

x1b1+x2b2+...xn*bn <= MAX

xi is in {0, 1} (not sure how to represent this constraint in the matrix but the example I keep seeing in introductions to Linear Programming is the "70 men, 70 jobs" problem and it has the same binary restriction, yet somehow it's guaranteed to be efficient)

Answer 1

Your problem seems to be a knapsack problem: it is NP-hard. As you noticed, it can be formulated as a linear program with binary constraints; most linear programming software packages also allow integral constraints, but those constraints can make them significantly slower.

The bipartite matching problem can also be formulated as a linear program with binary constraints, but it turns out that its relaxation, i.e., the same problem with the binary constraints $x_i \in \{0,1\}$ replaced by $0 \leqslant x_i \leqslant 1$, has integral solutions: the two problems are actually equivalent.

But this is the exception, rather than the rule: in general, binary or integral constraints do make the problem harder, and relaxing them only gives an upper (or lower) bound on the objective.