#ortools — Public Fediverse posts

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

#python #software #engineering

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

Решаем VRP-задачи, или Как мы в Додо доставку оптимизировали

Все сервисы доставки рано или поздно сталкиваются с аббревиатурой VRP. За ней скрывается сложная и важная задача оптимизации доставки. От того, насколько эффективно вы её решите, зависит и удовлетворённость клиентов, и реальные показатели бизнеса: скорость доставки, расходы на логистику. В этой статье я расскажу о типах VRP-задач, их отличиях, и о готовых решениях, которые вы можете затестить в ваших кейсах уже сейчас. Поделюсь подходами и инструментам, которые открыл в ходе исследования темы, опытом их использования и причинами, по которым я сразу отказался от некоторых из них.

https://habr.com/ru/companies/dododev/articles/904464/

#ORTools #Комбинаторная_оптимизация #VRP #Подбор_оптимального_маршрута #Алгоритмы #Транспорт #Курьерская_доставка #Логистика #Маршрутизация #Планирование_маршрутов

Permission granted: A role mining model

We implement a recently published role mining model using both constraint programming and mixed integer linear programming, then compare their relative performance while solving several examples.
https://www.solvermax.com/blog/permission-granted-a-role-mining-model
#orms #pyomo #ortools #python

Ortools — библиотека для решения задачи VRP

Привет! Меня зовут Илья Набатчиков, я MLE в компании Kamaz Digital. Также я являюсь учусь в онлайн магистратуре на базе университета ИТМО @ai-talent . Сегодня я хочу рассказать о библиотеке ortools для решения проблемы маршрутизации транспортных средств с учетом ограничений по времени и грузоподъемности (CVRPTW). И самое важно поделиться парой важных фичей, которых вы не найдете в документации.

https://habr.com/ru/articles/783754/

#ortools #комбинаторная_оптимизация #vrp

Production mix - Conclusions
We built a linear program in six Python libraries: #Pyomo, #PuLP, #ORTools, #Gekko, #CVXPY, and #SciPy.
This blog article summarizes our conclusions from using each of the libraries. We also indicate which library we prefer for various types of optimization modelling.
https://www.solvermax.com/blog/production-mix-conclusions
#orms #Python #DataScience #optimization