A true Traveling Salesman Problem on top of the Knapsack Problem takes longer than I want to spend (many minutes vs ~10s) and also does more than I want.

A forced-greedy TSP (near neighbors are all scored 1, farther nodes are all scored 0) is much faster and closer to what I want but still longer than I want (~2m)

The solution to a combinatorial problem is not a faster algorithm, it's a smaller problem.

I need to break the TSP into chunks and solve them separately. The difficult thing is that I need to do this while deliberately remaining unaware of the semantics of the nodes for larger architectural reasons.

#constraintprogramming #python #radar #orbit #scheduling #math #computerscience

#constraintprogramming #ortools #scheduling/#routing #optimization

I think I'm thinking about this wrong.

My basic problem is scheduling #radar collection intervals in continuous time. There are many constraints on the intervals already and that's all working (by which I mean "running"--I'm not actually connected to a radar yet).

However, I also want to put a constraint on interval *transitions* to make sure we don't require the dish to move instantaneously.

AFAIK, the only way to constrain adjacent items like this is via a circuit. So I was going to add a "circuit overlay" to the model. Then I could say that the "edge" from radar dwell A to radar dwell B had to be a certain time distance apart or whatever.

I'm writing a tiny test program to see how that works and it isn't doing what I expect.

But in debugging that, I think I just realized my entire plan doesn't work. There's no reason the circuit overlay is going to come out in the same order as the intervals as laid out in time. That voids the entire plan!

Also, even though all the kids are home for #christmas none of the #nerd are awake for rubber-duckying

GRRRRRRRRRRRRRR

#python #software #engineering

Did you know that you can watch short videos describing the research published in the Constraints Journal on ACP's YouTube account?

For example: here's a playlist with videos accompanying Vol 29: https://youtube.com/playlist?list=PLcByDTr7vRTa943JoLYbnbO6fG2HHM11F

#ConstraintProgramming #ACP #ConstraintsJournal #YouTube #SciComm #Science #Research #Optimization #CombinatorialOptimization #AI

Finally getting back to the #constraintprogramming #ortools #scheduling/#routing #optimization problem

I have a minimal working implementation of both a server and a selection of agents at various levels of realism. Two other #software peeps are making two real agents to talk to my server

...and I'm realizing I need to bump up my game and get ahead of them...again

For most of the scheduling types/agents, routing is a non-issue. For a couple types/agents it is absolutely crucial. It's one of those that is being implemented by one of the #engineers. And if answers come back unrouted, a higher-level person is going to absolutely POUNCE and start advocating Bad Ideas

So I was looking into circuit constraints and there isn't a lot of info out there beyond the basics.

Until I found this wonderful tutorial

https://github.com/d-krupke/cpsat-primer?tab=readme-ov-file

It covers everything from the beginning to advanced and and even niche usage, including such important things as runtime parameters and timing. All in #python!

#thanksgiving

So....for this #constraintprogramming thing

I have a bunch of individual job getting put into the solver. I'm requerying everything from scratch on every iteration because things can change and being responsive to that is exactly what this project is about.

However, I also want to keep the near future in the schedule relatively stable for a number of reasons. Human factors, for instance. Also there's some race conditions that can happen when the current time is within the duration of a job. Like what if the job disappears? Or if something just barely more important arrives--how valuable is avoiding rocking the boat vs doing the optimal task?

Ideally I would just hold the jobs in the near future as a constant. However, based on past experience I doubt the feasibility of even identifying "the same jobs" on each iteration (cf: "things can change" and also Ship of Theseus).

I've come up with a scheme that tries to hold the *gaps* between jobs as a (near) constant instead. That has its own complications.

Maybe I should go back to the original problem of trying to make the jobs identifiable even if they change....?

But that's not just hard, it also makes it the problem of a #software #developer in the future. (I'm not being thoughtful here, I'm being pessimistic that they'll do it right)

I guess I'll just Do The Best I Can on my end and make sure the users have the ability to control the rest.

Ugh.

#engineering

My #constraintprogramming #programming journey has been extremely interesting

In just a couple weeks (using google or-tools, but this isn't an endorsement) I've been able to make reasonable schedules

(the existing "schedule" example is helpful to learn the tool but essentially completely unlike the scheduling problem I'm doing. it's more knapsack-y but the example for that was only slightly more helpful.)

Building this much was really only supposed to be ammo to help me defend against some really bad ideas in an upcoming meeting. But it works so well it will almost certainly become the core of the future system.

My question is: To a zeroth order this is a knapsack problem. To a first order it is *also* a traveling salesman problem.

How dumb would it be to add TSP as a soft constraint? Pretty dumb, right?

Except I really do want to do it because that effect is extremely noticeable in some circumstances. Can I figure out how to limit that constraint to only situations where it applies?

#software #engineering #data #math