GLOP: Binary Decision Variables Are Not Binary In Solution

[Raghav]

Hello everyone. I am trying a problem related to graph traversal over graph G=(V, E), where a matrix X composing of xij (i, j belong to V)  of BoolVar type denoting whether edge (i, j) are being traversed or not.

I added a bunch of constraints and printed the X matrix. The funny thing is that values in X are not Boolean, but rather floats between 0 and 1. I understand that this is because I am using the GLOP_LINEAR_PROGRAMMER.

So, my question, any way to cleverly constraint xij to be either 0 or 1, or any modification I can make without turning my code upside down?

Details: Python3 (3.6.9) and OR-Tools (9.2.9972)

[Laurent Perron]

Of course, this is a simplex solver, and not a MIP solver.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f363b25d-7cae-4d85-ab47-5e0297fa2d5bn%40googlegroups.com.

[Raghav]

Indeed. I was wondering whether there is a clever mathematical way to constrain the values in X to be either 0 or 1? Or can I simply round off the values of X to 0 or 1 in the solution? Thank you.

[Laurent Perron]

Not with glop.

Solving the simplex is (pseudo)polynomial.

solving a MIP is NP-Hard.

Use a MIP solver like CP-SAT (if there are no continuous variables), or SCIP.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/783998c1-241e-4471-9174-ac05e95b1b7an%40googlegroups.com.

[Raghav]

Sorry for missing this. Yes, for anyone else in the same position too, SCIP was the way to go. Thank you sir.