Ucame across a paper today and this paper mentioned that the model size is $O(\mid I\mid\cdot\mid T \mid)$. I am also sitting on a MILP problem right now. Does my model size also amount to this size or is it different? If so, how do I find out what my model size is?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Are you familiar with the big O notation? $\endgroup$– fontanfCommented Jul 18, 2023 at 14:24
-
$\begingroup$ @fontanf Not really! $\endgroup$– Karl SeidlCommented Jul 18, 2023 at 14:27
-
$\begingroup$ Then that's where you should start en.wikipedia.org/wiki/Big_O_notation $\endgroup$– fontanfCommented Jul 19, 2023 at 8:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
First, the notation $O(\mid I\mid\cdot\mid T \mid)$ means that the model size grows in proportion to the product of the cardinalities of $I$ and $T.$ Whether this is relevant to you depends on whether you envision applying your model to progressively large problem instances. If you have one specific problem in mind, "big O" notation is not meaningful for your case.
For a given instance of your model, there are several size measures that are relevant, the primary ones being total number of constraints, total number of variables, number of integer/binary variables and number of nonzero coefficients. Many solvers will output this information for you. What to make of it is hard to say. Typically "more" implies "slower to solve", but it's not quite that simple. For instance, a reformulation of the original model that increases either the constraint or variable count (or both) but reduces the density of the coefficient matrix (basically, number of nonzero coefficients divided by product of constraint and variable counts) might be faster to solve than the original model ... or it might be slower.
-
$\begingroup$ Thank you very much, sir, for this detailed answer. Can you possibly recommend literature (with chapter) to read into the subject? $\endgroup$ Commented Jul 18, 2023 at 20:46
-
1$\begingroup$ Sorry, I don't recall seeing any books (or research papers) that dealt with model size, with the exception of asymptotic complexity as problem instances grow (the "big O" notation). $\endgroup$– prubin ♦Commented Jul 18, 2023 at 21:32