In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

Question

In what cases is solving Binary Linear Program easy (i.e. P complexity)?

The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to guarantee finding the global optimum within reasonable time, so any advice in that direction is most welcome.

I was under the impression that when solving a scheduling problem, where a variable value of 1 represents that a particular (timeslot x person) pair is part of the schedule, if the result contains non-integers, that means that there exist multiple valid schedules, and the result is a linear combination of such schedules; to obtain a valid integer solution, one simply needs to re-run the algorithm from the current solution, with an additional constraint for one of the real-valued variables equal to either 0 or 1.

Am I mistaken in this understanding? Is there a particular subset of (scheduling) problems where this would be a valid strategy? Any papers / textbook chapter suggestions are most welcome also.

Answer 1

It is not true that fractional solutions can necessarily be turned into integral solutions. For example, suppose that 1 requires either slots A and B, or slots D and E; 2 requires either slots B and C, or slots E and F; and 3 requires either slots A and C, or slots D and F. It's easy to check there is no integral solution at all (A,B,C together can accommodate at most one, and D,E,F together can accommodate at most one). However there is a fractional solution of giving everyone 1/2 of every slot that might possibly accommodate them.

There are conditions such as total unimodularity that guarantee that there are optimal integral solutions. In that case, the problem is in P, because all that is needed is to solve the LP relaxation which can be done in polynomial time.