0
$\begingroup$

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!

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 :) $\endgroup$
    – Ed_Silver
    Aug 24, 2023 at 15:53
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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