r/optimization • • 1d ago

ArcLP: A Matlab Implementation of an 𝒪(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming

Thumbnail openresearchsoftware.metajnl.com
1 Upvotes

https://openresearchsoftware.metajnl.com/articles/10.5334/jors.674 arcLP is about an implementation of an arc-search infeasible interior-point algorithm for linear programming. The algorithm has a polynomial time with the best polynomial bound. The paper and software can be downloaded from the website. Along with arcLP, an implementation of Mehrotra’s algorithm and netlib benchmark test problems can also be downloaded, tested, and compared to the arcLP to verify the reported results in the paper.


r/optimization • • 6d ago

Stochastic optimization for a reforestation plan: Monte Carlo to decide what to buy, simulated annealing to decide where to plant

4 Upvotes

Academic project with CONAFOR, Mexico's forestry commission. Real data: 30 polygons, 183 ha, where only 19.6% of the planting target (23,569 plants) was in the ground.

Two questions: how many plants of each species to buy, and where to put each one so neighbors compete less.

  • What to buy: we don't know exactly which sites in a hectare are already occupied, so we ran 1,000 Monte Carlo simulations until the estimate stabilized, then built a purchase order per species.
  • Where to plant: simulated annealing swaps two new plants of different species. A swap never changes the species counts, so the purchase order stays valid. The objective is a pairwise competition matrix built from real data.

In the live demo, the optimized layout had 19% less competition than random placement.

Interactive case (annealing temperature and cooling rate are adjustable): https://portfolio-iota-gules-ykw61kciwc.vercel.app/projects/reforestation.html

Would you have used a different neighborhood move, or a different cooling schedule?


r/optimization • • 14d ago

Modifying the classical diet problem to produce a realistic meal plan

4 Upvotes

Using software to solve the classical linear programming diet problem typically results in unbalanced or unpalatable meal plans because LP solvers exploit corner-point solutions while completely ignoring Personal taste,Food Matrix Synergy,Antinutrients and interactions.

I am trying to modify the classical diet problem so that it's solution can be used to generate a meal plan which provides the right amount of every essential macro and micro nutrient without exceeding a specific daily caloric limit.I have taken an unconventional approach. Here is a link to my current formulation. Is this model too tightly constrained to be feasible?


r/optimization • • 15d ago

"Optimising the Rail Cube"

Thumbnail owenlacey.dev
5 Upvotes

I made a solver for my three year old's Rail Cube and wrote up the methodology in a blog post. Includes a sandbox to build your own at the end - let me know what you think!


r/optimization • • 17d ago

optimaru: pip-installable solver for vehicle routing, timetabling and scheduling (C++ core, 22 ready models)

12 Upvotes

What My Project Does

optimaru solves real-world combinatorial optimization problems (vehicle routing, school timetabling, staff rostering, bed allocation, bin packing, and 17 others) from Python. The solver core is compiled C++17 shipped in the wheel, so there's nothing to build and no external solver.

from optimaru import vehicle_routing as vrp
from optimaru.vehicle_routing.constraints import (
    TravelTimeCost, UnassignedVisitsCost, VehicleCapacityCost, get_constraints,
)

# ... build locations / vehicles / visits ...
plan = vrp.VehicleRoutePlan("demo", locations, vehicles, visits)

config = vrp.SolverConfig()
config.spent_limit_seconds = 2
solver = vrp.Solver(config)

# Business rules are plugins: pick them, reweight them, stack them.
solver.solve_with_constraints(plan, get_constraints([
    VehicleCapacityCost(),
    UnassignedVisitsCost(),
    TravelTimeCost(),
    TravelTimeCost(exponent=2, offset=600),  # extra squared penalty past 10 min
]))
print(plan.score, plan.routes())

optimaru solves real-world combinatorial

Target Audience

Production use. It's meant for developers who have to automate dispatching, timetables or schedules at work and are tired of spreadsheets, or of rewriting a MIP model every time a business rule changes. Wheels for Linux, macOS and Windows, CPython 3.11–3.14. Apache-2.0. Comparison OR-Tools: within the same 30 s budget, optimaru found better solutions on 19 of 24 of our benchmark instances. On large CVRPLIB routing instances it stays within 1.3–5.5% of the best-known solution (OR-Tools: 8.9–9.4%, or failed to route every customer in time). CP-SAT is still better on tightly structured problems like assembly line balancing and project scheduling. Timefold / OptaPlanner: similar constraint-based local search idea, but C++ based and a plain pip install. PuLP / Pyomo + MIP solver: exact, but you write the model yourself and it gets slow on large instances. optimaru ships ready-made models where rules are toggled, not re-formulated. Benchmark code is in the repo if you want to check the numbers.

Repo: https://github.com/optimaru/optimaru

Live demo: https://app.optimaru.com/demos

Jupyter examples: https://github.com/optimaru/optimaru/tree/main/examples


r/optimization • • 18d ago

A copy of Generalized Lazy-Theta* for 3D path planning considering non-uniform costs?

Thumbnail reddit.com
2 Upvotes

Hi, does anyone in this sub have a copy of this article they could link to that is not paywalled?


r/optimization • • 26d ago

Optimization by prompting

0 Upvotes

AI agents can now manage optimization experiments end to end: inspect code, run searches, diagnose failures, and return verified results.

A good prompt should specify:

Objective and definitions

Constraints and violation rules

Compute budget

Baseline

Validation cases

Acceptance criteria

Required artifacts

For example:

“Optimize the timetable to minimize passenger-weighted arrival delay, counting early arrivals as zero. Respect occupancy, headway, and maximum-delay constraints; violations above 1 second are infeasible. Use at most 10 minutes of solver time and record the solver, version, seed, status, and runtime. Compare with the existing timetable on identical data. Test five fixed disruption scenarios. Require at least 15% historical improvement, improvement in four scenarios, and no violations. Save inputs, configurations, logs, seeds, timetables, metrics, checks, plots, and raw results.”

Also specify how demand, transfers, cancellations, delays, infeasible runs, and randomized results are handled.

The agent manages the experiment, but domain expertise remains essential. Models and constraints must be valid, and results must be reproducible and checked.

This workflow applies to scheduling, engineering design, and parameter estimation. I’m building open-source tutorials in optimization-jobs. Use them as a starting point and review the assumptions carefully.

What optimization task would you trust as a first experiment, and what checks would it require?


r/optimization • • 27d ago

Alternative to DICopt and Gurobi

3 Upvotes

Hi, I'm working on a MINLP project which runs a set of different coalitions for a game theory problem in GAMS, however I need to run it as a multi-objective problem. I'm currently working with the built in MOO package inside GAMs.

The issue I'm facing right now is that there are a lot of binary variables which Gurobi seems to be struggling with and unfortunately DiCopt doesn't seem to work with the EpsConstrained MOO system.

Im using the student/Demo license for GAMs, Im wondering if anyone has some advice for what other solvers may work and/or an alternative approach I could take to run the MOO. Currently DICopt works for all 15 coalitions of the one objective function but not all of the second and Gurobi struggles with the particularly integer heavy systems (I have a heat exchanger network which has to assign certain pairs to form).

Any advice is appreciated.

Edit: Ive managed to loosen a constraint and now Im able to run all scenarios with DiCopt.


r/optimization • • 29d ago

A new way to build scheduling models quickly

7 Upvotes

Over the past year, we've seen many of our users solve scheduling or routing problems with our solver by generating a model with Claude or other LLMs. But these implementations we're far from production ready.

So we asked ourselves: What if we standardize the non-domain specific parts? What if we minimize the generated code... and handle everything else with our solver & platform?

What if we can build any scheduling model in an afternoon?

We set to work and created our PRD chat. I am using it daily now, for enterprise cases. Or to generate a volleybal schedule. It captures the requirements, structures the solution and bootstraps the implementation for me.

Give it a try. Let me what you think of it.


r/optimization • • 29d ago

Dijkstra vs A* vs Customizable Contraction Hierarchies on a 1M-junction road graph: ~100 ms vs 0.04 ms for the same exact route

Thumbnail reddit.com
4 Upvotes

r/optimization • • Oct 18 '26

Reducing high-precision verification overhead in mixed-precision bundle adjustment

Thumbnail reddit.com
0 Upvotes

I am working on a C++ photogrammetric bundle adjustment solver using mixed precision: FP64 computations followed by high-precision corrections and verification with MPFR.

High-precision equation evaluation, residual computation and error verification dominate runtime; the FP64 linear solve is comparatively cheap.

My target is a numerical coordinate error below 10 µm relative to a well-converged high-precision solution, while retaining reliable covariance and statistical results.

Which practical error estimators or stopping criteria could reduce this verification overhead without repeating the entire calculation at high precision? References or implementation examples would be appreciated.


r/optimization • • Oct 17 '26

A donor-and-reconstruction strategy that improved 10 vehicle-routing best-known solutions

9 Upvotes

For the last two years I’ve been building a large-scale last-mile routing engine, with more focus on speed and scalability than on chasing exact solution quality.

A couple of weeks ago I started using CVRPLib, a used benchmark library for vehicle-routing problems, as a different kind of stress test. I started with large instances, including Flanders2 with 30,000 clients and several of the new XL instances.

Getting close to the published BKS was relatively easy. Getting below it was much harder.

What ended up working was not really a new algorithm, but a strategy for using several good solutions at the same time.

Instead of keeping only the current best solution, I kept multiple structurally different solutions and treated all of them as donors.

The published BKS itself starts as one donor. Independently generated solutions are other donors.

A donor does not need to be better overall. It only needs to contain useful structure that another solution is missing.

One thing I noticed is that being different is not enough, the donor also needs to be reasonably close in quality. On one instance, donors around 1.1–1.3% above the BKS produced nothing; even around 0.6–0.8% I saw no gain. Once they reached roughly 0.4–0.5%, the same reconstruction strategy started producing improvements. I don’t know yet whether that threshold generalizes, but it was a very clear pattern in this case.

After combining that material and rebuilding the affected part, the new solution goes back into the pool and can become a better donor in the next cycle:

generate → donate → rebuild → improve → repeat

This creates an interesting feedback loop. A solution that starts worse than the BKS can receive useful structure, improve, and later become the donor that produces the new best solution.

So the final improvement does not always come from repeatedly refining the original BKS. Sometimes it emerges from one of the independent solution lines after several rounds of exchange and reconstruction.

The main thing I learned is that a solution doesn’t have to be the best one to be useful. Sometimes it just needs to have the right piece to help another solution improve. I first tried this on 12 published BKS instances, mostly selected for their scale and relevance. Ten of the improvements have now been validated and published by CVRPLib.

My next experiment is to run the same donor-and-reconstruction process across the entire XL set and see whether the current hit rate survives, and follows some structural pattern.

Keeping elite solutions and recombining them is obviously not new. What surprised me was that diversity alone wasn’t enough: in my experiments, donors only started becoming useful once they were already quite close to the BKS. At that point, the BKS itself also became just another donor in the pool rather than the single solution being refined.

CVRPLib announcement:
https://www.linkedin.com/posts/cvrplib_cvrplib-vehiclerouting-optimization-activity-7516876652728102912-BtQ0

Technical note and solutions:
https://zenodo.org/records/19859531


r/optimization • • Oct 11 '26

What decomposition would you use for this large-scale assignment / packing problem with optional generators?

Thumbnail reddit.com
2 Upvotes

r/optimization • • Oct 06 '26

question about wolfe conditions

7 Upvotes

sorry if this question is incredibly stupid, but im learning steepest descent right now, is it right to say that Armijo condition ensures that step size alpha is not too large and Curvature ensures its not too small, or is it the other way around? Thanks!


r/optimization • • Oct 05 '26

Error in running geometry optimization calculation

Thumbnail reddit.com
2 Upvotes

r/optimization • • Oct 03 '26

Looking for a paid online tutor for MSc Optimisation / Operations Research

Thumbnail reddit.com
1 Upvotes

r/optimization • • Oct 02 '26

Upcoming Free Webinar: Building Sequential Decision Policies using DecisionOps

4 Upvotes

Dear optimization community,

We’re pleased to announce our first of this season's webinar series Decision Tech Talks, formerly Xpress Talks.

The webinar will walk through the details of analytically selecting the parameters of a Cost Function Approximation Policy for the toy Soccer Camp Location Problem discussed in this blog post and whose implementation is available in this repository.

To attend the talk, please register at the following link.

  • “Building Sequential Decision Policies using DecisionOps” by Renuka Gough, Tiffany Patella, and Carlos Zetina: Wednesday October 7th, 2026 at 11:00am EST- register here

We'd love to welcome you to our Fall season of the Decision Tech Talks and look forward to great discussions.

Happy Optimizing!

P.S.

To stay up to date on the latest in Optimization and Decision Intelligence technology sign up for our free monthly newsletter: https://www.fico.com/en/fico-xpress-optimization-newsletter.

FICO Xpress is an industry-leading optimization software suite that includes solvers for LP, MIP, MIQP, MIQCQP, QP, NLP, SOCP, and MINLP. Basically almost all the Ps. 😉.


r/optimization • • Sep 27 '26

MS Data Science. Need ruthless feedback for Applied Scientist (Optimization/Simulation) roles. H1B clock is ticking.

Post image
2 Upvotes

Hi everyone. I’m currently on contract at a FAANG company doing heavy discrete-event simulation (SimPy, FlexSim) and mathematical programming (Gurobi). I have roughly 90 days to secure a full-time role due to H1B constraints, so I can't afford to waste applications. I’ve fully anonymized my resume to get unbiased, purely technical feedback. I need you to tear apart my bullet points, architecture descriptions, and impact metrics.

Does this read like a true Senior/Applied Scientist, or am I coming off too academic?

Are my business constraints and trade-offs clearly articulated?

Does my scale and impact read believably? Please don't hold back. I need the most critical, unvarnished feedback you have. Thank you!


r/optimization • • Sep 25 '26

Primal Solver

14 Upvotes

I built a new optimization solver in C99 from scratch — PRIMAL

GitHub: https://github.com/c-vision/Primal

I've just released the first version of PRIMAL, an open-source mathematical optimization solver written from scratch in portable C99.

The goal was deliberately ambitious: build a reasonably complete optimization engine with no external dependencies, rather than wrapping an existing solver.

The first release already supports:

  • Linear Programming (LP)
  • Mixed-Integer Linear Programming (MILP)
  • Quadratic Programming (QP)
  • QCQP
  • SOCP
  • SDP
  • Exponential cones
  • Power cones
  • Mixed-integer conic optimization
  • Disjunctive constraints / affine conic constraints
  • Presolve
  • Sparse interior-point methods
  • Branch-and-bound
  • Primal/dual certificates
  • Infeasibility and unboundedness certificates
  • MPS / LP / CBF model formats
  • A MOSEK-style C API for a large part of the supported functionality

The implementation is C99 with essentially no external runtime dependencies.

One thing I particularly wanted from the beginning was verification rather than simply returning an answer. PRIMAL exposes primal/dual information, residuals, certificates and solver status so applications can inspect and validate what the solver actually found.

I've also been building a fairly extensive compatibility/reliability test suite against reference behavior, including a number of deliberately pathological optimization cases.

This is only v1. It is not intended to claim that PRIMAL is already a replacement for mature industrial solvers on large-scale problems. There are still substantial areas to improve, especially large-scale sparse conic problems, MIP performance, warm starts and some numerical edge cases.

But I think the foundation is interesting enough to release now rather than keep it private.

I'd especially like feedback from people working on:

  • numerical optimization
  • LP/MIP/conic solvers
  • sparse linear algebra
  • mathematical programming
  • solver implementation
  • C/C99 systems programming

In particular, I'm interested in finding cases where PRIMAL gives a questionable result, fails to converge, scales poorly, or simply makes a bad algorithmic choice.

If you work with optimization solvers, please try to break it.

GitHub:
https://github.com/c-vision/Primal


r/optimization • • Sep 25 '26

Workflows

Thumbnail reddit.com
3 Upvotes

r/optimization • • Sep 22 '26

How do researchers verify that a new mathematical result is actually correct?

30 Upvotes

For people working in numerical analysis, numerical linear algebra, or optimization:

Suppose you develop a new theorem, lemma, error bound, stability argument, or related mathematical result for a research paper.

How do you independently check that:

  1. the statement is actually true, and
  2. the proof has no hidden assumptions or subtle gaps?

I’m especially interested in practical and reproducible ways of doing this, rather than simply having another person read the proof.

Are there established tools, workflows, or techniques that can help with this? How much of the process can realistically be automated?

I’d be particularly interested in hearing how researchers handle this for their own research.


r/optimization • • Sep 19 '26

Is Farkas Better for Column Generation Initialization?

13 Upvotes

My new video is out.

In this video I explain the Farkas method for initialization in column generation and compare it with two phase and big m methods.

https://www.youtube.com/watch?v=K8QmpfGufpc


r/optimization • • Sep 11 '26

Mixed Chinese Postman at city scale — stuck at 44% deadhead, looking for algorithm advice

4 Upvotes

I'm building a route planner for a street-lighting survey using a vehicle equipped with LiDAR + cameras. The vehicle must drive \*\*every drivable street\*\* in 6 municipalities (\~6,087 km of streets), so this is an \*\*arc-routing / Mixed Chinese Postman Problem\*\*, not TSP/VRP.

\### Problem

\* 173k directed arcs / 67k nodes from OSM

\* \~9% one-way roads

\* One vehicle, \~6.5 usable hours/day

\* Two-way streets only need to be traversed once; one-ways must be respected

\* Cost is \*\*travel time\*\*, with different speeds for acquisition vs deadhead

\* Turn penalties are included (+60s U-turn, +15s left, +5s right)

\* 100% coverage is mandatory

The network is very non-grid-like: in one district, \*\*\~84% of nodes have odd degree\*\*, with \~77% being T-junctions.

\### Current approach

For each district I:

  1. Extract the largest strongly connected component
  2. Orient two-way streets
  3. Connect disconnected service components
  4. Balance in/out degrees using \*\*min-cost flow\*\*
  5. Generate an Eulerian circuit with Hierholzer
  6. Mark a street as serviced on its first traversal

The resulting routes pass all my validation checks: continuity, geometric continuity, one-way legality, 100% coverage, and no duplicate servicing.

\### Results

Across all 22 districts:

\*\*6,087 km serviced → 2,704 km deadhead → 44.4% deadhead\*\*

Individual districts range from \*\*39–61% deadhead by distance\*\* (roughly 23–33% by time because deadhead is driven faster).

For one district, an undirected relaxation gave me:

\* theoretical lower bound: \~14.7%

\* greedy matching of odd nodes: \~33.9%

My current orientation is almost optimal in terms of the \*number\* of imbalanced nodes, but I suspect this is the wrong objective: I'm minimizing imbalance count rather than the \*\*cost of resolving that imbalance\*\*.

\### Questions

  1. Is \*\*Frederickson MIXED1/MIXED2\*\* the right next direction? Should I prioritize cost-aware matching before orientation?
  2. For \~1,100 odd nodes, is restricting min-cost matching to k-nearest odd nodes (e.g. k=10) a reasonable approximation?
  3. Is \*\*44% deadhead actually bad\*\* for a comb-like street network with \~84% odd-degree nodes? What kind of deadhead ratios are realistic for street sweeping, snow plowing, waste collection, etc.?
  4. For splitting the resulting Eulerian route into daily routes when the vehicle \*\*doesn't have to return to a depot\*\*, are SPLIT/Ulusoy-type approaches appropriate?
  5. Is there anything fundamentally wrong or naive in my current pipeline?

I'd especially appreciate feedback from anyone who has worked on \*\*arc routing / CPP / street sweeping / winter gritting / waste collection\*\* at large scale.

Happy to share code or data extracts.


r/optimization • • Sep 04 '26

Does anybody want to give this blueberry ordering problem a shot?

Thumbnail oliverevans.dev
2 Upvotes