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

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.

• In general, the number of valid schedules (and also the number of optimal valid schedules) is unconnected to whether or not an LP solver's answer contains fractional values. Rerunning with a 0-or-1 constraint is indeed simple to do if you are working with a program that lets you do so, but in general the underlying software has to work much harder, since this will usually make the problem NP-hard. Sep 10, 2020 at 21:49
• I'm not sure there is a terribly useful characterization of which integer linear programs allow a polynomial-time solution; I think you'll have a better luck asking about the specific problem statement and how to solve it (even if there are no guarantees that the algorithms runs in polynomial time in the worst case).
– D.W.
Sep 10, 2020 at 21:50