7

Let $B$ and $I$ denote finite sets, let $$ E: I \times B \to \mathbb{R}_{> 0} $$ be a function, and let $s_b \in \mathbb{N}$ for $b \in B$ be given. Find $x_{i, b} \in \{ 0, 1 \}$, for $b \in B$ and $i \in I$ maximizing $$ \sum_{i \in I} \sum_{b \in B} E(i, b) $$ subject to the constraints: $$ \sum_{i \in I} x_{i, b} \leqslant s_b \quad \forall b \in B, \quad \text{and} \quad \sum_{b \in B} x_{i, b} \leqslant 1 \quad \forall i \in I.$$

Does anyone know how I might approach this problem?

The interpretation: we are assigning items $I$ to buckets $B$ where each bucket $b$ has a limited capacity $s_b$ (all items have the same size) and there is a value (benefit) $E(i, b)$ in assigning item $i$ to bucket $b$.

Example: a school has several courses $B$; each student $i \in I$ can be assigned to only one course; student $i$ has preference $E(i, b)$ for course $b$. Which students should be allocated to which courses to maximize happiness (the sum)?

popstack
  • 173
  • 4
  • 2
    This seems like it is a variant of a multiple knapsack problem where we enforce equality constraints instead of inequality constraints. You can be reasonably sure that something similar to your problem has been considered in the Operations Research literature. –  Jul 02 '12 at 16:10
  • I have asked the scicomp mods whether their community would be interested in fielding this one. –  Jul 02 '12 at 16:58
  • 1
    @whuber - yes, scicomp is happy to take it. Benjamin, the notation in your formulation is not quite clear to me. First, your definition of the function $\varphi$ is probably too broad, and you might want to consider tightening it. Second, I don't understand your constraint on the buckets. Shouldn't you be summing over the objects in each bucket and using a less than or equals constraint? Do you have a more specific example of what you're trying to do? – Aron Ahmadia Jul 02 '12 at 18:05
  • @AronAhmadia you're right about the size constraint, I should have been partitioning $\mathcal O$. I've edited the question. – popstack Jul 03 '12 at 08:57
  • Ben, I'm still a bit confused by your notation. Normally, we use $|.|$ notation to indicate a magnitude or size of a set, is that what you're doing here? As cardinal indicates, you're trying to solve something that looks like a multiple knapsack problem, which is going to require a mixed integer program solver. If you give us a specific example of your problem, we might be able to give you an example solution. – Aron Ahmadia Jul 03 '12 at 09:07
  • @cardinal that is a good connection -- indeed, my equality constraint is a special case of an inequality constraint. The significant difference with multiple knapsack is that a value is given to an assignment of an object to a bucket (via the function $E$), put differently, the value of an object depends upon the bucket it is placed in. – popstack Jul 03 '12 at 09:09
  • Thank you for bearing with me! A specific example: in a school, there are various courses ($\mathcal B$). Each student ($\mathcal O$) must study one and only one course. Each course accepts only a fixed number of students and there are exactly enough places for all the students. Given a matrix ($E$) of the preferences of each student for each course, where preferences can not be negative, how can the students be allocated to courses such that their collective happiness ($\sum_{o \in \mathcal O} E(o, \varphi(o))$) is maximized? – popstack Jul 03 '12 at 09:51
  • Should I reformulate the question to reflect it's resemblance with multiple knapsack and use an inequality constraint? Your comments have helped me realise that the formulation is not so natural. – popstack Jul 03 '12 at 09:53
  • 1
    Okay, this is an assignment problem. I would move your comment example up into the problem description itself. – Aron Ahmadia Jul 03 '12 at 11:15
  • 2
    EDIT: have significantly updated the question to reflect the helpful comments above. – popstack Jul 03 '12 at 12:36

2 Answers2

1

Isnt it a standard mixed-integer program (assume you multiply the objective coefficients with the corresponding variables)? You should be able to solve it with any MIP solver like scip (open source) or Gurobi (academic trial version) - at last for "not to big" instances.

Martin
  • 221
  • 1
  • 2
1

As other people have noted, your problem is a special case of a mixed-integer linear program, as long as your objective function is linear. (If your objective function is not linear, then it would be a mixed-integer nonlinear program, and I'd make different recommendations below.)

My recommendation is to use a software package like GAMS (free trial version for small problems), AMPL (free trial version for small problems), PuLP (Python, free), Coopr (Python, free), OSI (C++, free), or YALMIP (MATLAB, free) instead of a direct solver interface, unless you have a very clear idea of the solver you want to use (and that you may want to force potential users to use) for your application.

All of these packages focus much more on modeling your problem, and offer interfaces to multiple free and non-free mixed-integer programming solvers, which gives you much more freedom to experiment with choice of solver and high-level parameters, at the cost of speed and memory. This approach also gives you considerable flexibility to try alternative formulations and higher-level algorithms (things like Bender's decomposition, Dantzig-Wolfe decompositions, and so on) that solvers won't attempt for you with heuristics. (Mixed-integer programming solvers tend to focus more on heuristics for generating cutting planes, generating additional valid constraints, and exploring branch-and-bound trees.)

Once you have set your formulation, and you have an idea of the speed and memory requirements for your application, you can make the decision to choose among the many mixed-integer linear programming solvers out there for your problem. Furthermore, a lot of these solvers have multiple language interfaces; again, multiple factors (convenience, familiarity, performance requirements, project deadlines) will influence your choice of language.

Of particular note are the free, open-source solvers in the COIN collection (CBC, SYMPHONY, BCP, and others), GLPK, SCIP, and LPSOLVE, as well as the closed-source, professional packages CPLEX and Gurobi. You may also be able to find a solver that exploits the structure of the mixed-integer linear program instance(s) you've written above.

The professional packages tend to be considerably faster than the open-source solvers, but the professional packages are also expensive for non-academics. For CPLEX and Gurobi, it is possible to obtain fully functional licenses for free if you are at an academic institution; these will enable you to solve very large problem instances. CPLEX and Gurobi compete for the title of "fastest (mixed-integer) linear programming solver," whatever that means. The free solvers can also handle somewhat large instances, depending on problem structure; I've used free solvers to solve problems with a few thousand binary variables and a few thousand constraints, for instance.

Geoff Oxberry
  • 30,394
  • 9
  • 64
  • 127