Skip to main content
7 votes
Accepted

Is 0-1 knapsack problem still NP-Hard (1) with an equality constraint and (2) when all the weights in the constraint are equal to one?

The general case where not all weights are equal to one, is ${NP}$ hard, as the subset sum problem reduces to it with a constant objective function. If all weights $w_i$ are equal to one, the problem ...
Sune's user avatar
  • 6,657
2 votes

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

Without the group score it's a very easy problem. With the group score it becomes (for an open-source solver) a very difficult problem, even though the number of auxiliary variables isn't very high. ...
Reinderien's user avatar
2 votes

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

There are at least two approaches that can be used to model this. The more obvious one uses binary variables $x_{wsd}$ equal to 1 if and only if worker $w$ is scheduled in slot $s$ on day $d.$ Some of ...
prubin's user avatar
  • 39.8k
1 vote
Accepted

Optimal way to formulate a piecewise linear function

I don't think you can gainfully avoid the binary variables (or SOS constraints). Some solvers directly support piecewise linear functions, but I'm pretty sure that means added binary variables under ...
prubin's user avatar
  • 39.8k

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