Or really, I should just rewrite this as a VRP, since it is so close to that anyway and the code I have was just a prototype.
#constraintprogramming #python #radar #orbit #scheduling #math #computerscience
#ConstraintProgramming
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
This radar scheduling thing is dominated by a Knapsack Problem with a dash of Traveling Salesman to keep from wearing out hardware/looking dumb.
I think I have a workable solution to each of these now.
It took a little while to get the TSP portion to behave usefully. It's funny, because you'd think getting a "feasible" solution would be easier than an optimal one. But in terms of software it's much more difficult--you have to define "feasible".
The TSP-relevant tasks are the GEO satellite belt. These objects are spread out in a mostly-linear ~150deg azimuthal band that is somewhat clustered. You might have 5 objects within a degree of each other and then nothing for 3 degrees.
Inside these clumps, I don't care about the path much. But I definitely don't want to zip back and forth between clumps.
I can't limit to a set time since other jobs may intervene. I can't do it as a percentage since I don't know what percentage these jobs are at ay given time.
What I ended up doing is basically defining the costs just like I described them above. We have "close' objects (within say 3 degrees) that all have the same cost. Then medium and and large distance.
For a problem with more time than jobs, I get a reasonable answer in 3s. With more jobs than time, I just set a 10s upper bound and still get a reasonable time.
I need to integrate this solution with the larger program to really check runtimes with a more realistic set of jobs. But I think I have enough understanding and knobs in place to make this work.
#constraintprogramming #ortools #scheduling/#routing #optimization #python #software #programming #engineering
#constraintprogramming #ortools #scheduling/#routing #optimization
I think I may have gotten this working in the toy problem. I can get a list of time-ordered optional intervals AND a circuit in the same order. That will let me put sequential constraints at the circuit level (I hope)
The key turned out to be to make sure all present intervals were also entered nodes AND that every x->y edge meant that x.time < y.time....and that the reverse is not true!
It's weird how confused I am by half-reified constraints, given that's *exactly* how programming languages do variable assignment.
a = b
makes a take the value b, but not vice versa.
#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
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!
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.
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?
This paper compares MILP and CP solvers on a new FJS scheduling problem, showing CP is faster and "warm starts" are vital for large instances. https://hackernoon.com/the-tortoise-and-the-hare-an-unexpected-scheduling-race-between-milp-and-cp-solvers #constraintprogramming
A performance showdown for Job Shop scheduling. This study pits MILP, CP, and new heuristics against a fresh set of challenging problem instances. https://hackernoon.com/pitting-heuristics-against-exact-solvers-in-the-flexible-job-shop-gauntlet #constraintprogramming
This article formalizes DAG-based FJS with position-based learning via a MILP using position variables plus a CP Optimizer model. https://hackernoon.com/algorithms-that-learn-as-they-schedule-a-twin-model-approach-to-modern-fjs #constraintprogramming
Only a few days left to apply!
If you are interested in logic, decision-making, reasoning under uncertainty and statistics, apply by the end of this month for an opportunity to work with me, dr. Sicco Verwer and dr. Fabian Mies at Delft University of Technology!
Application deadline: 31 August 2025
#AcademicJobs
#AcademicMastodon
#GetFediHired
#AcademicJob
#SymbolicAI
#Statistics
#AI
#ConstraintProgramming
#CombinatorialOptimisation
#SensitivityAnalysis
#FormalMethods
#CombinatorialOptimization
#Delft
#TUDelft
#AcademicChatter
One month left to apply!
If you are looking for a PhD position and are interested in working on probabilistic inference, sensitivity analysis, and decision-making, this might be the job for you! We are looking for candidates with a strong background in Computer Science, and ideally also in Mathematics.
Please apply by 31 August. We're looking forward to reading your application!
#AcademicJobs
#AcademicMastodon
#GetFediHired
#AcademicJob
#SymbolicAI
#Statistics
#AI
#ConstraintProgramming
#CombinatorialOptimisation
#SensitivityAnalysis
#FormalMethods
#CombinatorialOptimization
#Delft
#TUDelft
#AcademicChatter
Hi everyone,
I feel like a re-introduction is long overdue!
My name is Anna, and I'm an assistant professor of Algorithmics at the Delft University of Technology, specialising in combinatorial optimisation, symbolic AI, constraint programming, propositional model counting, operations research and reasoning under uncertainty.
I'm a nerd, a feminist and a traveller, not always in that order.
In my spare time I like to hike and go geocaching. I try to go swing dancing a few times a week. I am a Trekkie. I want to learn how to draw. I am an Indomie and Obsidian enthusiast. Based in the Netherlands, I miss Belgium, Canada and Singapore.
Since a job in academia somehow always is personal, I have chosen to mix professional interactions with the more personal ones on this platform. At least for now. Obviously, my opinions do not necessarily reflect those of my employer yadiyadiyada.
Hope to keep interacting with you all!
#Introduction #AcademicMastodon #Algorithmics #SymbolicAI #CombinatorialOptimisation #ConstraintProgramming #ModelCounting #OperationsResearch #ProbabilisticInference #Geocaching #LindyHop #Jazz #SwingDancing #Hiking #Obsidian #StarTrek #Travel #TUDelft #MastoMiGoreng #Indomie #GNUTerryPratchett #Catstodon #Mastocats #Caturday #ExpatLife #MakanApaToda
Congrats to ir. Roy Katz for successfully defending his MSc thesis: "Adding Ejection Chain to Nurse Rostering Simulated Annealing Solver"!
https://latower.github.io/posts/2025/06/roy-defends/
#AcademicMastodon #ConstraintProgramming #NurseRostering #ConstraintOptimization #CombinatorialOptimisation #StudentLife
I am hiring!
I have a fully funded PhD position available for someone with an interest in logic and statistics, at Delft University of Technology (Netherlands).
Application deadline: 31 August 2025
#AcademicJobs #AcademicMastodon #GetFediHired #AcademicJob #SymbolicAI #Statistics #AI #ConstraintProgramming #CombinatorialOptimisation #SensitivityAnalysis #FormalMethods #CombinatorialOptimization #Delft #TUDelft #AcademicChatter
6/6
❔ How to Nominate
⏳ Deadline: end of 22 June, 2025, AoE
📝 To nominate a paper, please fill in this form: https://forms.gle/V4eYuGKGSHjokpBw7
A nomination may come from anyone. Posthumous awards will be considered. All papers can be found online on the Springer webpage: https://link.springer.com/journal/10601/volumes-and-issues
Help us recognise and celebrate the research that has shaped our field, and submit your nomination today!
#BestPaperAward #ConstraintProgramming #AI #CallForNominations #Optimization #AcademicMastodon
5/6
✅ Evaluation Criteria
Factors influencing the decision of the award include: - Did the paper start a significant new line of research? - Has the paper made a major theoretical advance? - Has it heavily influenced other researchers (whether in or outside CP?) - Has the paper influenced applications?
#BestPaperAward #ConstraintProgramming #AI #CallForNominations #Optimization #SpringerPublishing #AcademicMastodon
3/6
🏆  Prominent Paper Award
This award honours papers that are exceptional in both their significance and impact on the field of Constraint Programming, and that were published in Constraints between 2018 and 2024 (inclusive).
The publication year refers to the publication year of the issue in which the paper appeared.
#BestPaperAward #ConstraintProgramming #AI #CallForNominations #Optimization #SpringerPublishing #AcademicMastodon
Client Info
Server: https://mastodon.social
Version: 2025.07
Repository: https://github.com/cyevgeniy/lmst