dr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽง4d ago

Thank the goddesses for my recent attempts at #music transcription and also for #adhd #rx

My #constraintprogramming #radar #scheduling talk is in *gulp* two weeks. My rough draft is due FRIDAY.

5 years ago, I spent a week in front of blank slides, sometimes in tears, unable to even conceive of a method by which I could start.

Earlier this week, I did at least manage to gather a lot of content slides from other decks but as of this morning it was all just a jumble.

This morning I took a two-pronged approach

1. Clear the runway: Do dumb things like checking my inbox, getting a drink and music squared away, etc first. THEN take meds and dive in as they ramp up.

2. I was having trouble getting started but also specifically having trouble with the start of the slides. But there's no reason the first slide in the deck has to be the first one created.

For the song I've been working on transcribing, I gave up on "note by note from the beginning" approach. Instead I found spots where it was easy to figure out (single sustained notes, simple melodic progressions, etc). Then I tied those together knowing where the mystery passage had to start and end.

Why not do the same thing with PowerPoint? I definitely know what I want to say in the "design proposal" section. And I think I know what some future work will be. Start with those parts!

That only took like 30 minutes. And with that out of the way, it looked a lot more do-able to find some points to make in the "how did we get here" section.

I now have a (very) rough draft of the talk!

Show threadConstraints JournalFeb 23

2/2 Here are some highlights. Read the full paper here: https://link.springer.com/article/10.1007/s10601-025-09383-0

#ConstraintProgramming #Security #Cryptology #Cryptography #CryptographicHashFunctions #ConflictDrivenClauseLearning #BooleanSatisfiability #MD5 #SHA1 #SHA256

Constraints JournalFeb 23

1/2 Exciting news: we just published a new paper: "Preimage attacks on round-reduced MD5, SHA-1, and SHA-256 using parameterized SAT solver", by Oleg Zaikin

If you are interested in security, cryptology, or Constraint Programming, definitely give this paper a read!

https://link.springer.com/article/10.1007/s10601-025-09383-0

#ConstraintProgramming #Security #Cryptology #Cryptography #CryptographicHashFunctions #ConflictDrivenClauseLearning #BooleanSatisfiability #MD5 #SHA1 #SHA256

Show threadLinotype PilgrimFeb 14
" #AliceML is a #functionalprogramming language based on Standard ML, extended with rich support for concurrent, distributed, and #constraintprogramming." #plt #computerscience www.ps.uni-saarland.de/alice/

Alice
Alice

Show threaddr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽงJan 20

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

dr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽงJan 20

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

Show threaddr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽงDec 29

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

Show threaddr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽงDec 19

#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.

dr ๐Ÿ› ๏ธ๐Ÿ›ฐ๏ธ๐Ÿ“ก๐ŸŽงDec 18

#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

Constraints JournalDec 3

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