Linear method to determine costs between elements of a sequence

Question

I am using OR-tools to create a certain optimal production sequence. Here, i have to schedule N products, where each one is exactly scheduled once.

I have an array of N by N, denoting the costs from/to a product. The objective is to create an order O such that the costs are minimized.

Issue: I ofcourse cannot index my costs array by using o[n], as exemplified below, but I haven't managed to find a method that mimics this behaviour and is linear. In a future state, I may need the costs from the n-th element to the n+z-element (z being an integer) so it needs to be scalable. Any suggestions?

Note I am aware that this is very similar to a TSP/ routing problem, and open to such suggestions as well. If there are particular callbacks that can look more than 1 step ahead/back, I am eager to hear. For instance, a callback with multiple from_nodes and a single to_node.

N = 5

# costs array from product n to n
arr = np.random.randint(1, 11, size=(N, N))




model = cp_model.CpModel()
solver = cp_model.CpSolver()

o = {}

for n in range(N):
    o[n] = model.NewIntVar(1, N, f'order_{n}')

# example order 5 -> 3 -> 1 -> 2 -> 4

    
# schedule each element once 
model.AddAllDifferent(o)


    
# costs from one element to the next    
costs = sum(
    
    arr[o[n]][o[n+1]]
    
    for n in range(N)
    ) 

model.Minimze(costs)

status = solver.Solve(model)

I am aware that this is close or similar to a TSP problem, and open to solutions of such kind as well.

Answer 1

First,

your data is quadratic, so a linear solution seems unrealistic

Second, you can have a look at: https://github.com/google/or-tools/blob/d37317b17ca16658451cafe05085fc22c39dd6c8/examples/python/single_machine_scheduling_with_setup_release_due_dates_sat.py#L447

The bottom line, there are two approaches:

• use a circuit constraint as shown in the example above
• count how many objects are before you (as implemented in the expansion of the reservoir constraint

both have pros and cons.