1
$\begingroup$

I am an electrical engineer who is currently working with some bench table placement problem, and suddenly my problem look pretty much like the set cover problem here. After that, some of my colleague told me that most problem in engineering is quite sparse and this should be exploited.

Therefore, my question is:

Can sparse set cover problem be solved or approximated more efficiently comparing to its non-sparse counter part ?

$\endgroup$

1 Answer 1

4
$\begingroup$

For a given set of dimensions, a sparse model is likely to be faster to solve than a dense one simply because fewer nonzero coefficients mean less arithmetic per iteration of whatever algorithm you are using. However, there is no guarantee that a specific sparse instance will solve faster than a specific dense instance of the same dimension.

As for exploiting sparsity, if you are using an integer programming model and an IP solver, there is a good chance that the IP solver internally exploits sparsity (for instance, by using matrix factorization techniques that benefit from sparsity).

$\endgroup$
2
  • $\begingroup$ Thank you ! Such a great insight. Could you please be nore specific on what kind of matrix factorisation technique for sparse set cover problem ? $\endgroup$ Commented Jan 1 at 1:03
  • 1
    $\begingroup$ What I had in mind was not specific to set covering problems. For a general linear or mixed integer linear programming problem, you have a linear constraint set $Ax=b$ which, for a given basis, is partitioned into a basic part ($Bx_B=b,$ with $B$ nonsingular) and a nonbasic part ($Nx_N = 0,$ with $x_N = 0.$ In textbooks (and old solver codes) you would solve $Bx_B = b$ by inverting $B.$ Current practice does not invert $B$ but rather factors it, perhaps using an LU decomposition, perhaps SVD or some other decomposition. (I'm being vague because I'm not a solver author.) $\endgroup$
    – prubin
    Commented Jan 1 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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