We got 1000 items with a weight Wk, we have :
Wk=max[(1-Xm)*Wm+Pk]
with Xk a binary variable if we put the item or not
Xm the weights of related items "m" to the item "k"
Pk the basis weight of item k.
In this article, the authors get results in approximately the same run time as we do with a different algorithm:
http://www.optimization-online.org/DB_FILE/2016/10/5695.pdf
If you are unsure of the CPLEX result, you should investigate the CPLEX LOG file about that execution.
On my CPLEX Log i get this and it seems alright for me,
Tried aggregator 2 times.
MIP Presolve eliminated 4049889 rows and 5626 columns.
MIP Presolve modified 531000 coefficients.
Aggregator did 590 substitutions.
Reduced MIP has 3143 rows, 2504 columns, and 7568 nonzeros.
Reduced MIP has 1221 binaries, 1283 generals, 0 SOSs, and 0 indicators.
Presolve time = 3,20 sec. (2755,32 ticks)
Found incumbent of value 5,0798177e+29 after 4,01 sec. (2982,42 ticks)
Probing time = 0,00 sec. (0,62 ticks)
Tried aggregator 1 time.
Reduced MIP has 3143 rows, 2504 columns, and 7568 nonzeros.
Reduced MIP has 1221 binaries, 1283 generals, 0 SOSs, and 0 indicators.
Presolve time = 0,03 sec. (5,80 ticks)
Probing time = 0,00 sec. (0,61 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0,03 sec. (9,99 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 5,07982e+29 3991,0000 100,00%
* 0+ 0 5,07945e+29 3991,0000 100,00%
* 0+ 0 5,07930e+29 3991,0000 100,00%
0 0 1,16200e+24 9 5,07930e+29 1,16200e+24 772 100,00%
0 0 1,16296e+24 9 5,07930e+29 Cuts: 2 773 100,00%
* 0+ 0 4,53025e+29 1,16296e+24 100,00%
0 2 1,16296e+24 9 4,53025e+29 1,16296e+24 773 100,00%
Elapsed time = 4,48 sec. (3103,58 ticks, tree = 0,01 MB, solutions = 4)
* 10+ 1 8,10436e+24 1,16296e+24 85,65%
* 250 190 integral 0 2,06712e+24 1,56296e+24 1983 24,39%
* 293 125 integral 0 2,05276e+24 1,56296e+24 2120 23,86%
* 333 25 integral 0 2,04476e+24 1,56296e+24 2363 23,56%
* 369 59 integral 0 1,86672e+24 1,57948e+24 2562 15,39%
* 386 55 integral 0 1,86304e+24 1,57948e+24 2615 15,22%
* 463 55 integral 0 1,71932e+24 1,57948e+24 2701 8,13%
* 507 32 integral 0 1,66672e+24 1,58396e+24 3116 4,97%
* 540 26 integral 0 1,66240e+24 1,61300e+24 3499 2,97%
* 573 34 integral 0 1,65156e+24 1,61300e+24 3325 2,33%
* 583 10 integral 0 1,64292e+24 1,61468e+24 3854 1,72%
Implied bound cuts applied: 10
Gomory fractional cuts applied: 1
Root node processing (before b&c):
Real time = 4,45 sec. (3105,28 ticks)
Parallel b&c, 8 threads:
Real time = 0,88 sec. (259,99 ticks)
Sync time (average) = 0,24 sec.
Wait time (average) = 0,02 sec.
------------
Total (root+branch&cut) = 5,33 sec. (3365,27 ticks)
It appears that CPLEX finished optimization and that CPLEX presolve did a good job it eliminating 4049889 rows and 5626 columns. So CPLEX did what it is being asked.
If you are still unsure of the results you could try with some benchmark instances if available in order to compare execution time and to possibly find problems with your model.
To be completely sure you could prove that your model is equivalent to the problem you solve. On the other hand I don't remember that CPLEX did something wrong. It either failed to complete the job (memory or time limit) or the model was incorrectly implemented. I hope that this remarks were useful.
Thank you M. Zoran Maksimovic for your answer. Sadly there isn't much benchmark for my problem, besides one article that used genetic algorithm to solve the problem. And to prove the equivalence, it's a bit tricky because we linearized the first model that represents the problem. It's just the fact that our problem is smilar to the quadratic knapsack problem which is NP-hard make us doubt our run-times.
Typical algos of KP problem are cited in this website : https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
For the special aspect of relation between weights is just an approximation to an other problem of the longest path in a tree and where weights are in fact times.
Usually for a knapsack problem, we need some idea of the total size capacity of the knapsack, as well as the size and value of each item to be placed in it. If the Wk depends on some other weights, it would be nice if we could pre-compute these; if the weights depend on the VARIABLE (not yet decided) Xm, there is potentially a problem. Your notation for the max operator is unclear. Are you taking the maximum over two numbers? Can you explain your full problem with notation?
A simple knapsack with 1000 variables is easy -- see Martello and Toth -- so I am not surprised with the run time. A true "quadratic knapsack" where there are interdependent choices is a much more challenging problem.
http://www.or.deis.unibo.it/kp/KnapsackProblems.pdf
- Badges
- Science topic
- Similar topics
- Theoretical Physics
- Time