Discussion @ 1394. Ships. Version 2 @ Timus Online Judge

can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Posted by test_tset 12 Feb 2014 18:39

Re: can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 14 Feb 2014 19:35

At least, it can be written as linear programming problem. However, it is INTEGER linear programming problem, which still remains to be NP-hard.

Re: can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Posted by test_tset 2 Aug 2014 12:28

can we use simplex() to solve floating version of lp, then use it as heuristics:

brute force to search in descending order of veriable x..

I will try this approach to test case 70(toooooooooooooo hard....)

Discussion of Problem 1394. Ships. Version 2