18 votes

Solving a knapsack problem with a lot of items

For the knapsack problem, you just use the Pisinger's code. It implements an exact algorithm, it is the fastest algorithm known in the literature, and it is open-source: http://hjemmesider.diku.dk/~...
user avatar
13 votes
Accepted

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Your linear program is similar to a mathematical formulation of a bounded Knapsack problem and has a similar linear relaxation. First note that $x_1$ is only restricted by $x_1\geq -1$ and thus $x_1=-...
user avatar
  • 2,685
10 votes
Accepted

Allocating credit card points

With the OP's clarifications I would say this is a straight-forward variant of the knapsack problem where you want to pack as many saved dollars into your budget of points. Find below the simple ...
user avatar
  • 1,323
9 votes
Accepted

How to optimize on a fixed-cost based on number of results?

You can linearize the objective as follows. Let binary decision variable $x_i$ indicate whether item $i$ is chosen, and let binary decision variable $y_c$ indicate whether the count of chosen items is ...
user avatar
  • 22.7k
9 votes

Solving a knapsack problem with a lot of items

A comprehensive comparison of different approaches to solving the knapsack problem is given in the recent paper1 by Ezugwu et al., where the authors compare the performance of the following approaches ...
user avatar
  • 8,350
9 votes

Confusion Between Different Types of Optimization Problems

I'm inclined to treat "discrete optimization" and "combinatorial" optimization as synonyms, but I'm not sure everyone does. "Integer programing/optimization" is a ...
user avatar
  • 31.1k
8 votes

Allocating credit card points

This seems like some sort of knapsack problem: Suppose you have a set of purchases and a certain amount of points. Each purchase can be "paid" by points as a whole, no partial usage of points for each ...
user avatar
  • 2,677
8 votes
Accepted

Optimize for bonuses within a group (knapsack)

If I understand correctly, binary variable $g_j$ indicates whether group $j$ is special, binary variable $a_{i,j}$ indicates whether exactly $i$ items are taken from group $j$, and binary variable $...
user avatar
  • 22.7k
7 votes
Accepted

Solving weekday and weekend fare movies

So it costs \$13 for the two of them on a weekday and \$24 for the two of them on a weekend. If you want to maximize the number of movies, skip the expensive ones and the \$100 budget yields $\lfloor ...
user avatar
  • 22.7k
7 votes
Accepted

0-1 knapsack with non-linear objective function

Even though knapsack problems are relatively easy to solve in practice, there does not exist a polynomial-time algorithm to solve even the standard knapsack problem, unless $\mathcal{P}=\mathcal{NP}$. ...
user avatar
7 votes

Allocating credit card points

That sounds like you could formulate it as MIP. You have a fixed set of planned purchases, right? Each of them ($p$) will yield a constraint of the form $x_p + c_p \cdot y_p = t_p$, where $x_p$ is ...
user avatar
7 votes
Accepted

Looking for books in the same style as Hans Kellerer 2004, Knapsack Problems

I waited some time but apparently no easy answer here. Thanks for providing some more hints in the comments to your question. One specialty about the knapsack book is: it is a monograph, that is, ...
user avatar
7 votes
Accepted

Mixed Integer Programming/Optimization using the Genetic Algorithm

It is possible (but a bit tricky) to write a mixed-integer linear program for this problem. If you are willing to accept a good but not guaranteed optimal solution, though, the GA is easily modified ...
user avatar
  • 31.1k
7 votes
Accepted

Knapsack - How to optimize bonuses for each pair of items

One approach is to introduce the pairs dynamically only when needed. Initially, solve a relaxation where every pair yields the highest bonus. (Note: I am suggesting to relax the objective and not to ...
user avatar
  • 22.7k
6 votes
Accepted

knapsack problem with non-linear constraint

Hold the phone... You can keep this linear. Just sum the selection variables and multiply by the min average requirement. No division required. ...
user avatar
  • 250
6 votes

Is there a knapsack problem which allows 'out-of-capacity'?

If "out of capacity" means "if you violate capacity, you get infinite capacity for a large cost" the problem reduces to solving a knapsack problem and checking if the profit of ...
user avatar
  • 5,445
6 votes

Is there a Bin Packing Library similar to TSPLIB?

BPPLIB – A Bin Packing Problem Library: http://or.dei.unibo.it/library/bpplib
user avatar
  • 22.7k
6 votes
Accepted

Looking for a similar optimization problem

If "total duration" means sum of durations, this is called the generalized assignment problem. If "total duration" means maximum of durations, this is called the bottleneck ...
user avatar
  • 22.7k
6 votes
Accepted

Knapsack problem with negative value and weights and cardinality constraint

I assume you have a solver for knapsack problems with cardinality constraints, but it wants only non-negative coefficients. Let $$\color{darkblue}U_{min} := \min\{0,\color{darkblue}u_1,...,\color{...
user avatar
5 votes
Accepted

Combinatorial optimization, implementation needed

It seems what you are looking for, is the maximum dispersion problem. The following blog post discusses a MIQP formulation along with a number of different MILP formulations http://...
user avatar
  • 5,445
5 votes
Accepted

A variant of maximum sum subarray problem?

If all $B_{i,j}$ are known, you can solve the problem via integer linear programming as follows. Let binary decision variable $x_{i,j}$ indicate whether entry $(i,j)$ is selected, let binary decision ...
user avatar
  • 22.7k
5 votes
Accepted

Dynamic program for knapsack in $O(W)$ space?

There is a recursive scheme which makes it possible to retrieve the optimal solution with an $O(n + W)$ memory. It is described in Section 3.3 of the book "Knapsack Problems" (Kellerer et al....
user avatar
  • 1,741
4 votes

How to solve knapsack problem with simulated annealing?

Simulated annealing is just a (meta)heuristic strategy to help local search to better escape local optima. Local search for combinatorial optimization is conceptually simple: move from a solution to ...
user avatar
  • 2,717
4 votes

Does this problem fall into any common problem definition....Knapsack maybe?

Here is a MILP formulation, in case you did something different. Let binary variable $F_j$ indicate whether subset $j$ is chosen. Let binary variable $T_i$ indicate whether item $i$ appears in two ...
user avatar
  • 22.7k
4 votes

Solving a variant of multiple knapsack problem/ generalized assignment problem

It looks like there is no relationship between different knapsacks, so you can solve this exactly as $m$ independent 0-1 knapsack problems. Also, for knapsack $j$, you can eliminate any items $i$ ...
user avatar
  • 22.7k
4 votes

Is there a knapsack problem which allows 'out-of-capacity'?

You can introduce a nonnegative surplus variable $y$ with large cost $M$ and maximize $\sum_j v_j x_j-M y$ subject to $\sum_j w_j x_j \le W+y$. Alternatively, if you want to impose a one-time fixed ...
user avatar
  • 22.7k
4 votes

knapsack problem with non-linear constraint

Here is a workaround for your nonlinear problem: ...
user avatar
  • 8,350
4 votes

Combinatorial optimization, implementation needed

Let $x_{i}$ be a binary variable that takes value $1$ if item $i \in I_k$ is selected. You want to choose $n$ items from each set $I_k$, so impose $$ \sum_{i\in I_k} x_{i} = n \quad \forall k $$ You ...
user avatar
  • 10.4k
4 votes
Accepted

Dynamic Programming - Formulating recurrence relation

You have an instance of the 0-1 knapsack problem where you want to determine which teams to select to maximize the number of wins, subject to a budget. The linked page provides a DP recurrence, which ...
user avatar
  • 22.7k
4 votes

A variable being a set...?

This is a constraint programming (CP) model. The "vocabulary" of MIP solvers is fairly standard. They all recognize real, integer and binary variables, linear equality and inequality ...
user avatar
  • 31.1k

Only top scored, non community-wiki answers of a minimum length are eligible