--- title: How Benders Decomposition Works Part I: Optimality Cuts description: Benders decomposition is a powerful optimization technique that splits mixed-integer programs into a master problem (handling strategic/binary decisions) and a... canonical: https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: How Benders Decomposition Works Part I: Optimality Cuts | daily.dev og:description: Benders decomposition is a powerful optimization technique that splits mixed-integer programs into a master problem (handling strategic/binary decisions) and a... og:url: https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg og:image: https://api.daily.dev/og/posts/z42rABXGG.png og:image:alt: How Benders Decomposition Works Part I: Optimality Cuts og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # How Benders Decomposition Works Part I: Optimality Cuts **[Towards Data Science](https://daily.dev/sources/tds)** · 34 min read · 0 upvotes · 0 comments ## Summary Benders decomposition is a powerful optimization technique that splits mixed-integer programs into a master problem (handling strategic/binary decisions) and a subproblem (handling operational decisions). The master iteratively proposes solutions, the subproblem evaluates them via LP duality, and optimality cuts are added to progressively tighten the master's cost estimate until lower and upper bounds converge. The post walks through the algorithm's history, derives optimality cuts from LP duality theory, solves a toy example by hand step-by-step, then applies the method to the uncapacitated facility location problem. A full Python implementation using Pyomo and the open-source HiGHS solver is provided, converging in 9 iterations on a 5-facility, 20-customer instance. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### What is a Benders optimality cut and how is it derived? A Benders optimality cut is an inequality added to the master problem, derived from the dual solution of the operational subproblem for a fixed strategic decision. Every feasible dual solution provides a lower bound on the operational cost, and substituting the dual variables into the dual objective expression yields a cut that remains valid for other strategic decisions, not just the one just evaluated. _Developers modeling large optimization problems can dig deeper into cut generation techniques on daily.dev._ ### How do you implement Benders decomposition for the uncapacitated facility location problem in Python? Using Pyomo with the HiGHS solver, the facility-opening variables and a theta variable approximating assignment cost form the master problem, while a dual assignment subproblem is solved each iteration to generate optimality cuts added via a ConstraintList. For a 5-facility, 20-customer instance, this outer-loop algorithm converges to the optimal cost of 14,743 after nine iterations. _Anyone building iterative optimization pipelines can find implementation walkthroughs like this via daily.dev._ ### Why might Benders decomposition fail to outperform solving the full monolithic optimization model? For small instances, a modern solver can often solve the complete monolithic model almost immediately, making the overhead of constructing separate master and subproblems, transferring solutions, and generating cuts across iterations more costly than beneficial. Benders decomposition pays off mainly when the problem has exploitable structure or when the monolithic model is too large to fit in memory. _Engineers weighing decomposition against monolithic solvers can compare trade-offs like these on daily.dev._ ## Similar posts on daily.dev - [How Benders Decomposition Works, Part II: Feasibility Cuts](https://daily.dev/posts/how-benders-decomposition-works-part-ii-feasibility-cuts-dsunoqnzk) · Towards Data Science · 0 upvotes · 0 comments - [Benders’ Decomposition 101: How to Crack Open a Stochastic Program That’s Too Big to Swallow Whole](https://daily.dev/posts/benders-decomposition-101-how-to-crack-open-a-stochastic-program-that-s-too-big-to-swallow-whole-ysaazrtpa) · Towards Data Science · 0 upvotes · 0 comments - [The Budget Split That Explains Itself](https://daily.dev/posts/the-budget-split-that-explains-itself-wrmej8r4y) · Towards Data Science · 0 upvotes · 0 comments - [Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt](https://daily.dev/posts/scaling-decision-optimization-to-100-million-variables-and-beyond-with-mpdlp-in-nvidia-cuopt-aqavcibww) · NVIDIA Developer · 0 upvotes · 0 comments --- Tags: [#python](https://daily.dev/tags/python) [View this post on daily.dev](https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"How Benders Decomposition Works Part I: Optimality Cuts","url":"https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg"},"datePublished":"2026-07-31T12:56:42.973Z","dateModified":"2026-09-14T08:43:24.063Z","description":"Benders decomposition is a powerful optimization technique that splits mixed-integer programs into a master problem (handling strategic/binary decisions) and a...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/d88ffb48bc4d02ff6a2c0ea82651ef47?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/d88ffb48bc4d02ff6a2c0ea82651ef47?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Towards Data Science","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Towards Data Science","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/tds","url":"https://daily.dev/sources/tds"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"python","timeRequired":"PT34M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Towards Data Science","item":"https://daily.dev/sources/tds"},{"@type":"ListItem","position":3,"name":"How Benders Decomposition Works Part I: Optimality Cuts"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/how-benders-decomposition-works-part-i-optimality-cuts-z42rabxgg#faq","mainEntity":[{"@type":"Question","name":"What is a Benders optimality cut and how is it derived?","acceptedAnswer":{"@type":"Answer","text":"A Benders optimality cut is an inequality added to the master problem, derived from the dual solution of the operational subproblem for a fixed strategic decision. Every feasible dual solution provides a lower bound on the operational cost, and substituting the dual variables into the dual objective expression yields a cut that remains valid for other strategic decisions, not just the one just evaluated. Developers modeling large optimization problems can dig deeper into cut generation techniques on daily.dev."}},{"@type":"Question","name":"How do you implement Benders decomposition for the uncapacitated facility location problem in Python?","acceptedAnswer":{"@type":"Answer","text":"Using Pyomo with the HiGHS solver, the facility-opening variables and a theta variable approximating assignment cost form the master problem, while a dual assignment subproblem is solved each iteration to generate optimality cuts added via a ConstraintList. For a 5-facility, 20-customer instance, this outer-loop algorithm converges to the optimal cost of 14,743 after nine iterations. Anyone building iterative optimization pipelines can find implementation walkthroughs like this via daily.dev."}},{"@type":"Question","name":"Why might Benders decomposition fail to outperform solving the full monolithic optimization model?","acceptedAnswer":{"@type":"Answer","text":"For small instances, a modern solver can often solve the complete monolithic model almost immediately, making the overhead of constructing separate master and subproblems, transferring solutions, and generating cuts across iterations more costly than beneficial. Benders decomposition pays off mainly when the problem has exploitable structure or when the monolithic model is too large to fit in memory. Engineers weighing decomposition against monolithic solvers can compare trade-offs like these on daily.dev."}}]} ```