9

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 $c$. Let $w_i$ be the weight of item $i$, and let $b_c$ be the bonus/penalty for choosing $c$ items. The problem is to maximize $$\sum_i w_i x_i + \sum_c b_c ...


7

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 $b_i$ indicates whether exactly $i$ items are taken from the special group. You want to enforce the logical implication $$b_i \implies \bigvee_j (g_j \land a_{i,j}...


7

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 100/13 \rfloor = 7$ movies. If you prefer writing it explicitly as an optimization (yes, knapsack) problem, let integer decision variables $x$ and $y$ be the ...


7

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}$. The knapsack problem can be solved in pseudo-polynomial time $\mathcal{O}(nC)$. Even when the input length (=number of digits describing the problem) is small, ...


6

BPPLIB – A Bin Packing Problem Library: http://or.dei.unibo.it/library/bpplib


5

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://yetanothermathprogrammingconsultant.blogspot.com/2019/06/maximum-dispersion.html?m=1


4

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 can optimize whatever you want with these variables. If you want to maximize the $\ell_1$ distance between each pair of items, you are going to need a pairwise ...


4

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 is obtained by conditioning on whether or not you select the next team. The optimal objective value for your instance is 28: \begin{matrix} \text{team} & ...


3

I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing $\leq$ to $=$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ...


2

For the 2D and 3D variant you can find multiple instances as well as instance generators here: https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing https://www.euro-online.org/websites/esicup/data-sets/


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