0
$\begingroup$

Suppose I have a data set where the letters are patients $(a-z)$ and the numbers are screening procedures $(1-6):$

a:  1,2,3,5
b:  1,2,3
c:  2,1,6
.
.
.
z: 1,2,3,4,5,6

Each screening procedure has an associated cost and by removing certain screening procedures, the hospital can allocate resources elsewhere.Thus,the objective function is maximized if I remove as many of the screening procedures as possible.The constraint however is that at least 50% of the patients should have their screening procedures unchanged(not removed). Also, if I remove a screening procedure, the change is applied across all users. What are some good optimization algorithms to deal with this type of problem? This is just an example data set, so the real data set will contains millions of rows(for each patient) and hundreds of different procedures. I was thinking simulated annealing,hill climbing are good starting points. Are there better methods?

$\endgroup$
0
$\begingroup$

If your input is small enough, integer programming will give you the optimal solution.

However if you have millions of rows, this will not work, as integer programming algorithms do not run in polynomial time.

Indeed, heuristics, or metaheuristics are the way to go in this case.

$\endgroup$
  • $\begingroup$ So in this case are hill climbing and simulated annealing solid approaches? Are there any "big data" optimization algorithms that are similar to integer programming algorithms? $\endgroup$ – phil12 Nov 27 '15 at 2:42
  • $\begingroup$ simulated annealing or hill climbing are popular meta heuristics, but they do not guarantee optimality. There are many more, such as tabu search, genetic algorithms, grasp algorithms, greedy algorithms, etc…they are all suitable for big data, but very different from integer programming, which is the only one that is "purely" mathematical. Another approach could be dynamic programming, but I don't think it is possible for every problem. $\endgroup$ – Kuifje Nov 27 '15 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.