2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Commented Sep 10, 2020 at 21:49
  • $\begingroup$ 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). $\endgroup$
    – D.W. ♦
    Commented Sep 10, 2020 at 21:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.