# Tag Info

18

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/~pisinger/codes.html

13

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=-1$ at optimality. The sum of remaining variables is bounded by $1-k$ (indeed has to be equal to $1-k$) and since variables with lower indices have higher value ...

10

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 formalization where the index $i$ spans across all items on the current bill: Capacity of the knapsack: $C$ = Available points Item weight: $w_i$ = number of ...

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 ... 9 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 both in small size and large size problems: Genetic algorithms, Simulated annealing, Branch and bound, Dynamic programming, Greedy search algorithm, ... 8 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 purchase is viable. Let's declare some sets and parameters: let P={1,\ldots,n} be the set of purchases which each get a number to distinguish them. For each ... 8 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, ... 7 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 the amount of money you will spend on that purchase,$y_p$the amount of points with the conversion rate (per purchase) and$t$the total price.$x \ge 0$would ... 7 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, written by the same author(s). There are only few other books about a particular combinatorial optimization problem, with theory and algorithmic components, and ... 7 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 to handle it. The key is to use a chromosome of 10 real values, where the sixth through tenth are rounded down to the next lower integer and used to index a ... 6 Hold the phone... You can keep this linear. Just sum the selection variables and multiply by the min average requirement. No division required. import pyomo.environ as pyo v = {'hammer': 1, 'wrench': 3, 'screwdriver': 1, 'towel': 2} w = {'hammer': 5, 'wrench': 7, 'screwdriver': 4, 'towel': 3} limit = 14 M = pyo.ConcreteModel() M.ITEMS = pyo.Set(... 6 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 this is higher than all positive profits summed minus the large cost. 6 BPPLIB – A Bin Packing Problem Library: http://or.dei.unibo.it/library/bpplib 6 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 generalized assignment problem. You might also find something useful by searching for makespan minimization. 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 5 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 variable$r_i$indicate whether row$i$is selected, and let binary decision variable$c_j$indicate whether column$j$is selected. The problem is to ... 4 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 another one by changing some (generally a few) decisions, and then evaluate if this new solution is better or not than the previous one. For an introduction to ... 4 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 or more of the chosen subsets. The problem is to minimize$\sum_i T_isubject to: \begin{align} \sum_j F_j &= 140 \tag1 \\ \sum_j M_{i,j} F_j - 1 &\le ... 4 It looks like there is no relationship between different knapsacks, so you can solve this exactly asm$independent 0-1 knapsack problems. Also, for knapsack$j$, you can eliminate any items$i$that have$p(i,j)\le 0$. 4 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 cost$M$if there is any violation, let$y$be binary and change the constraint to$\sum_j w_j x_j \le W+Uy$, where$U$is some upper bound. 4 Here is a workaround for your nonlinear problem: solver_manager = SolverManagerFactory('neos') #solver = pyo.SolverFactory("BARON") solution = solver_manager.solve(M, solver = 'couenne') #solver.solve(M) for i in M.ITEMS: print(i,':',pyo.value(M.x[i])) You can either use a local nonlinear solver like BARON, or some solvers in NEOS server. I ... 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} & ... 4 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 constraints, maybe some quadratic stuff and maybe indicator constraints. CP languages and solvers are much less standardized. Apparently MiniZinc has a construct for ... 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 ... 3 This is not too big of a leap from the basic Knapsack problem and can be handled with only 3 constraints for the bin size, all-or-nothing, and the prohibited placements. Below is an example that I think fits the design pattern. This is casted in pyomo. I think OR-Tools is pretty similar in structure. It should not be a major leap. # multi-knapsack, ... 3 According to the attached file: In the$m$-dimensional bin packing problem ($m$-BPP) there are many large boxes of equal sizes, which are called bins, and the objective is to pack all$n$items into a minimum number of bins. We can translate any$m$-BPP instance into an instance of$(m+1)$-SPP (strip packing problem), where the additional$(m+1)$st ... 3 Unfortunately, I also do not know how to embed 0-1-knapsack specific inequalities with the odd number solution requirement. However, I know how to generate cuts that will reduce the search space whenever an even number of items is picked. So, let$x^{*} \in \mathbb{R}^{n}$be an optimal, eventually fractional, solution. If$\sum_{j} x^{*}_j\$ is an integer ...

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