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 MAX. My initial thought was to use linear programming (let me know if this is not the correct route).

I think I came up with the correct objective function and constraints but then I realized I would need an additional constraint to make sure the choice of an item x_i was an integer, in particular, 0 or 1. But I read that integer programming is not guaranteed to be efficient like linear programming even if it's binary.

But, my main confusion is that the example used to show the efficiency is assigning 70 jobs to 70 men which requires finding a value of 0 or 1 for each pairing of man and job, which is integer programming. 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).


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 my 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) = r1*x1+r2*x2+...+rn*xn

These were my constraints:

x1*b1+x2*b2+...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)

  • 1
    $\begingroup$ Welcome to Math.SE. Thank you for your question. We will be able to better help you if you share the example that you're having trouble with. In general, integer programming is harder (i.e. slower) than linear programming. $\endgroup$ – vadim123 Apr 28 '13 at 4:20
  • $\begingroup$ I updated the question with exactly what I'm trying to solve. Hope that helps. $\endgroup$ – Mastid Apr 28 '13 at 13:59
  • $\begingroup$ Mastid, it is helpful to have more details, but that's not nearly enough to understand what's going on. Perhaps you could give a small example of the type of problem you're trying to solve, as well as the details of how you're trying to solve it. $\endgroup$ – vadim123 Apr 28 '13 at 14:25
  • $\begingroup$ I've added more details. Let me know if there's something I still need to clarify $\endgroup$ – Mastid Apr 28 '13 at 15:02

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.


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.