3
votes
Np-hard sequencing or packing problems with total ordering between elements
Scheduling problems requiring a total ordering of the tasks are generally called sequencing problems in the OR literature. Car sequencing is one of the most famous ones. The car sequencing problem is ...
- 3,031
2
votes
A sum with a product-penalty
You might consider using dynamic programming, as in the usual binary knapsack problem. Let $f(n,k,C)$ be the optimal objective value for the original problem. Conditioning on the value of $x_n\in\{0,1\...
- 33.6k
2
votes
A sum with a product-penalty
One way is to replace the product part with its log. So if $z=\prod_i (1-x_i(1-b_i))$, this can be substituted with $\sum_i \log(1-x_i(1-b_i))$ or simply $\sum_i x_i \cdot \log b_i$.
This 2nd ...
- 3,513
2
votes
Accepted
BIP for Sudoku naturally integral?
The creators of the Sudoku puzzles ensure players that there is a unique solution to the puzzle. Hence, the system of integer linear equalities over Boolean variables described in Vanderbei's slides ...
- 3,031
2
votes
complexity Partitioning with negative numbers
Let $I = \{a_i, i = 1, \dots, n \}$ be an instance of "Partition with only positive numbers" that we want to solve.
Let $I' = \{4 a_i, i = 1, \dots, n \} \cup \{ -1, -1 \}$ be an instance ...
- 2,673
Only top scored, non community-wiki answers of a minimum length are eligible