3
$\begingroup$

I am very new to OR. I am trying to find the minimum cost sequence for a set of tasks that need to be executed. These tasks (at least some of them) have precedence constraints. For example, task T1 has to be completed before task T2 can be executed. I am planning to use TSP to solve this problem. But I am unable to find a solver that will accept precedence constraints to a TSP problem or at least I don't know how to set precedence constraints for a TSP problem. I have looked at Google OR tools. Can someone suggest a solver (preferably open source) that will accept precedence constraints or tell me how I can set precedence constraints in Google OR tools?

Edit 1: Context: OK let me try to explain why I am looking at TSP and why I am solving the problem I have using a multi-optimization algorithm. I have resources/agents that have to execute the tasks in a given time window. The task is to visit various locations in a contained area and do one of many operations in that location. I can/have to group these tasks based on a few parameters and assign them to an agent. The combinatorial search space is huge (as I am sure it is the case with most OR problems). So I have decomposed the problem into 3 parts- first find an initial batching of tasks that can be assigned to a unique agent based on various parameters, the second will solve for the shortest path (in terms of total completion times) that the agent would take to execute the tasks within each batch and the third part will assign the batch of tasks to an appropriate agent taking into account the deadline for each batch (minimizes weighted tardiness). This is done iteratively to get to the optimal batching,route & assignment without tardiness.

$\endgroup$
10
  • $\begingroup$ 1) Are you sure you want to go the TSP route? I would only do that, if you have sequence-dependent setup-times. If not, scheduling-approaches are probably much more efficient. 2) With TSP approaches it's not easy due to those being arc-focused (A immediately follows B) which makes global reasoning of precedences tough (transitive-closure is huge). 3) TSPTW is a better candidate as you then have some tour-accumulation (e.g. time or counting). 4) The accumulation approach is exactly what or-tools routing-solver would ask you for: see their example routing/samples /cvrptw_with_precedences.cc. $\endgroup$
    – sascha
    Feb 21 at 12:14
  • 1
    $\begingroup$ A bit more on or-tools: There is a non-trivial decision to be made as or-tools is an umbrella project with many different components where, depending on your approach, two (!) very (!) different (!) solvers are candidates for you: the routing-solver (from the example above) and the cp-sat solver. In most cases i would use the latter. While risking some misleading info, this one is (opposed to the routing-solver): a complete-method, exploits more typical scheduling-substructures and supports parallel-processing. Seq-dep costs can be modelled. Downside: scalability with many nodes! $\endgroup$
    – sascha
    Feb 21 at 12:25
  • $\begingroup$ Thanks for the alternate idea using scheduling. I should explore the feasibility of scheduling for the problem that I am solving. I am trying to solve a multi-optimisation problem wherein I am solving for a sequence of tasks (a batch) that minimises total completion time and these batch of tasks (to be executed in a time window) are then assigned to agents. These tasks usually have precedence that need to be satisfied. I have decomposed the problem into two parts - one TSP which solves for the best route (sequence of tasks) to take and the other HFVRPTW. $\endgroup$ Feb 21 at 14:43
  • $\begingroup$ Is it possible to set precedence constraints for TSP in cp-sat solver? $\endgroup$ Feb 21 at 14:44
  • $\begingroup$ Everything is possible. But there are good chances, that you don't want build a TSP with precedences (aka assignment-polytope) in CP-SAT, but a (disjunctive-)scheduling problem. As most scheduling-models are disjunctive , solvers like cp-sat follow the interval-var modelling- (and solving) approach and a precedence is just a simple inequality. or-tools has tons of examples (making use of various programming languages): routing an scheduling. Learn from those. Your problem still sounds more like scheduling than routing to me. Maybe start with or-tools/cp-sat job-shop-scheduling examples. $\endgroup$
    – sascha
    Feb 21 at 15:45

1 Answer 1

0
$\begingroup$

Can someone suggest a solver (preferably open source) that will accept precedence constraints?

Timefold is an open source solver that can handle TSP with precedence constraints.

Your model would look like this in Java (similar for Kotlin and soon Python):

@PlanningEntity
class Salesman {

    // Decided by the solver
    @PlanningListVariable
    List<Task> tasks;

}

@PlanningEntity
class Task {

   String id;
   List<task> precedenceTasks;

   // Automatically filled in based on the decisions by the solver
   @InverseRelationShadowVariable
   Salesman salesman;

   // Automatically filled in based on the decisions by the solver
   @IndexShadowVariable
   Integer salesmanTasksIndex;

}

The constraint would look like this:

.forEach(Task.class)
.join(Task.class,
     // Same salesman (optional)
     equal(Task::salesman),
     // Task 1 is before task 2
     lessThan(Task::salesmanTasksIndex))
// Task1 has task2 as a precedence
.filter((task1, task2) -> task1.precedenceTasks.contains(task2))
// Stop doing this!
.penalize(HardSoftScore.ofHard(1))
.asConstraint("Precedence tasks");

The Vehicle Routing and Food Packaging quickstarts source code can also give inspiration.

$\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.