7
$\begingroup$

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)?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Jul 2, 2012 at 16:10
  • $\begingroup$ I have asked the scicomp mods whether their community would be interested in fielding this one. $\endgroup$
    – whuber
    Jul 2, 2012 at 16:58
  • 1
    $\begingroup$ @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? $\endgroup$
    – Aron Ahmadia
    Jul 2, 2012 at 18:05
  • 1
    $\begingroup$ Okay, this is an assignment problem. I would move your comment example up into the problem description itself. $\endgroup$
    – Aron Ahmadia
    Jul 3, 2012 at 11:15
  • 2
    $\begingroup$ EDIT: have significantly updated the question to reflect the helpful comments above. $\endgroup$
    – popstack
    Jul 3, 2012 at 12:36

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\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.