I am solving an MILP maximization problem by LP relaxation, followed by simply truncating fractional values. The resulting objective value is only ~1% lower than the optimal MILP solution, as the LP relaxation returns mostly integer values.
The Constraint matrix A is not Totally Unimodular (TU), but the part pertaining to the Integer Variables is TU, i.e. in Ax
I don't know any theory on partial unimodularity but I can suggest use cuts of Gomory. Something like this ⌊A⌋ x ≤⌊b⌋
To the best of my knowledge, partial unimodularity in the technical coeffcients matrix A does not guarantee integrality of the solution. In order to get an integral solution, the matrix should be completely unimodular.
In http://sydney.edu.au/engineering/it/~mestre/papers/lagrangian.pdf it is stated that good approximations for partial unimodular MILPS (in this case set covering problems) is an open question.
This seems to be a recent topic as in a very recent seminar (https://web.math.princeton.edu/~svanzwam/talks/20130312.pdf) several issues beyond total unimodularity where shown.
This reference will also help:
https://www.google.es/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&ved=0CFIQFjAD&url=http%3A%2F%2Foptlab.mcmaster.ca%2Fcomponent%2Foption%2Ccom_docman%2Ftask%2Cdoc_download%2Fgid%2C145%2FItemid%2C92%2F&ei=b6DrUYOWJvCu7AbdxICwDQ&usg=AFQjCNEtH3Dli2PFTZBF3rIz7Noz21a7hA&sig2=vJ4TkXkPV4Gfdeop3qZmXw&bvm=bv.49478099,d.ZGU
In your situation and as I believe this is just a coincidence, I would look for a counterexample, i.e., generate many MILPS changing input data and check if in all cases the integer variables which have unimodular technical coefficients always end up being integer in the linear relaxation.
One colleague (Federico Perea) has helped us with this question. Here is a couple of counter examples.
1) If your A matrix does not contain the RHS vector, this model has a unimodular matrix for the technical coefficients of the integer variables but the linear relaxation has variables with non-integer values:
min x+y, s.t.: x + y >= 1; y >= 0.5; x>= 0.5; y \in {0,1}.
optimum solution: OF: 1.5 (y=1, x=0.5).
linear relaxation: OF: 1 (y=0.5, x=0.5).
2) If your matrix includes the RHS there are also counterexamples:
min y, s.t; y - x >= 0; x>= 0.5; y \in {0,1}.
optimum solution: 1.
optimum solution with linear relaxation 0.5
So it seems that even if the technical coefficients submatrix for the binary/integer variables is totally unimodular, the linear relaxation is not guaranteed to have integral values for these variables.
Thank you very much Ivan and Rubén (and Federico Perea) for your helpful answers, I appreciate it!
Hi,
It seems that there is an approximation algorithm for optimization problems with partially unimodular constraint matrixes, but for covering problems (not for packing problems that you asked), i.e., for problems like this:
min cx s.t. Ax
Thank you very much Konstantinos for this informative reply, I will definitely look into it.
In our recent WiOpt paper (https://home.iitm.ac.in/abhishek.sinha/WiOpt_2019.pdf), we encountered one such ILP, which has at most one fractional variable at an optimal solution. Please take a look at Theorems 4 and 5.
- Badges
- Science topic