# Tag Info

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