19
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/~...
- 1,394
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=-...
- 2,705
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 ...
- 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 ...
- 29.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 ...
- 8,567
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 ...
- 37.4k
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 ...
- 2,727
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 $...
- 29.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 ...
- 29.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}$. ...
- 6,033
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 ...
- 2,306
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, ...
- 5,889
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 ...
- 37.4k
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 ...
- 29.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.
...
- 252
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 ...
- 6,212
6
votes
Is there a Bin Packing Library similar to TSPLIB?
BPPLIB – A Bin Packing Problem Library:
http://or.dei.unibo.it/library/bpplib
- 29.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 ...
- 29.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{...
- 2,472
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://...
- 6,212
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 ...
- 29.7k
5
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 ...
- 2,910
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....
- 2,376
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 ...
- 29.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$ ...
- 29.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 ...
- 29.7k
4
votes
knapsack problem with non-linear constraint
Here is a workaround for your nonlinear problem:
...
- 8,567
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 ...
- 12.8k
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 ...
- 29.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 ...
- 37.4k
Only top scored, non community-wiki answers of a minimum length are eligible