Which algorithms could be suitable for solving my disjunctive programming problem?

Question

Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this question, I'll go into more depth in regards to my specific problem in case there is a better solution.

I am looking for an algorithm that can arrange tasks in a non-overlapping manner, whilst also satisfying a reasonably open set of possible conditions - ie: task 1 must happen before task 2, task 2 happens before a set time, task 1 is favoured to happen during the day.

I understand that one abstraction of this problem involves sets of inequalities, some of which must be disparate. This leads to the need for disjunctive rather than linear programming (if my understanding of the reply to my previous question is correct). For example:

x1 < x2 - d1 OR x2 < x1 - d2 //task x1 and x2 cannot overlap
x3 < x2 - d3 OR x2 < x3 - d2 //task x3 and x2 cannot overlap
x1 < x3 - d1 //task x3 must happen after x1
x1 < 100 //task x1 starts before 100
min( [start times st. dev. or similar] ) //example cost function

where x1, x2, x3 are the start times for tasks (variables to be solved) and d1, d2, d3 are their durations (constants).

The mathematician in my brain sees these sets of inequalities as inefficient however, as their number goes up with the factorial O(n!) so if anyone knows a more suitable approach please do not hesitate to let me know!

Any information you can add is much appreciated, but I am hoping for the name of an algorithm that can solve this sort of problem - preferably one already implemented in C# or with a C# wrapper.

Thanks everyone in advance!

Answer 1

The prior answer already explained a standard way to solve this kind of problem: introduce boolean (0-or-1) variables to model the disjunction, and then solve with an off-the-shelf integer linear programming (ILP) solver.

Answer 2

What about using a local search solver like Timefold or LocalSolver? In particular, LocalSolver has a C# API, which seems to address your need.

• Ed_Silver: Thank you for your answer, I will look into timefold! Localsolver seems to be a paid solution. I should have specified but this makes it unsuitable for me. Thanks again :)

Answer 3

You can use CPLEX to solve by modeling your problem as MIP or CP.

For the MIP algorithms in CPLEX is branch and cuts algorithms.

For the CP algorithm in CP Optimizer is filter method.

You can refer the official website in Cplex to realize the detailed.

MIP Solver CP Opimizer