{"id":17267,"date":"2026-07-31T12:28:55","date_gmt":"2026-07-31T12:28:55","guid":{"rendered":"https:\/\/techtrendfeed.com\/?p=17267"},"modified":"2026-07-31T12:28:57","modified_gmt":"2026-07-31T12:28:57","slug":"how-benders-decomposition-works-half-i-optimality-cuts","status":"publish","type":"post","link":"https:\/\/techtrendfeed.com\/?p=17267","title":{"rendered":"How Benders Decomposition Works Half I: Optimality Cuts"},"content":{"rendered":"


\n<\/p>\n

\n

army planners with coordination issues on a scale that had not often been imagined. Plane, personnel, gas, gear, coaching, and provides needed to be allotted throughout an immense system, usually below extreme time strain and uncertainty. This setting accelerated the event of operations analysis, a self-discipline based on the concept that advanced choices could possibly be studied systematically by knowledge, scientific reasoning, and arithmetic slightly than addressed solely by expertise and instinct [1].<\/p>\n

George Dantzig was among the many researchers immersed on this new world of large-scale planning. Throughout the struggle, he labored for the US Military Air Forces, the place he contributed to the evaluation and planning of army operations. After the struggle, the Air Power challenged him to assist mechanize planning processes that had beforehand been carried out largely by hand. In 1947, Dantzig formulated the overall linear programming downside and developed the simplex methodology, offering a scientific process for locating the perfect allocation of restricted assets amongst competing actions [2, 3]. This analysis continued by Venture SCOOP, the Scientific Computation of Optimum Packages, and later on the RAND Company, which turned one of many principal facilities for the early growth of linear programming and mathematical optimization [2].<\/p>\n

This mathematical revolution ultimately reached the Shell Laboratories in Amsterdam, the place Jacques Benders started working in 1955. Collectively along with his workplace mate, Guus Zoutendijk, he encountered troublesome refinery-planning issues involving manufacturing choices, materials flows, processing assets, and prices. After visiting Shell\u2019s Californian department and studying in regards to the potential of linear programming, they returned to the Netherlands and started implementing the simplex methodology for manufacturing planning within the refinery and petrochemical industries. Mathematical optimization promised to assist coordinate industrial techniques whose many interconnected choices might simply overwhelm unaided human reasoning [4].<\/p>\n

Nevertheless, the promise of linear programming got here with a irritating limitation. It labored fantastically when choices might fluctuate repeatedly, corresponding to how a lot materials to course of, produce, or transport. Many necessary industrial choices weren’t steady. They required selecting an possibility or rejecting it, activating another or leaving it unused, and answering sure or no. Introducing these discrete variables reworked an in any other case manageable linear program right into a a lot more durable mixed-variable optimization downside. Benders targeted exactly on this complication. In 1959, he and two Shell colleagues introduced an algorithm for linear packages containing binary variables at a RAND symposium, reporting computational experiments carried out on a Ferranti Mark I laptop whose addition time was roughly 1.2 milliseconds [4].<\/p>\n

Benders might have searched just for a sooner method to resolve the whole mannequin, however as a substitute he questioned whether or not the whole mannequin wanted to be solved suddenly. The discrete variables created a lot of the problem, but as soon as their values have been fastened, the remaining choices usually shaped an peculiar linear program. This urged a unique technique: isolate the complicating choices, permit one downside to decide on them, and let a second downside decide their operational penalties. As an alternative of treating the optimization mannequin as an indivisible object, Benders divided it into elements that would talk with and progressively enhance each other [5, 6].<\/p>\n

This perception produced one thing extra refined than merely fixing two smaller issues. The primary downside, which we now name the grasp downside<\/strong>, proposes a high-level determination whereas initially possessing solely an incomplete understanding of its true penalties. The subproblem<\/strong> evaluates that proposal and returns mathematical data exhibiting the place the grasp has been too optimistic. This data is transformed into a brand new constraint, referred to as a Benders minimize<\/strong>, and added to the grasp earlier than it tries once more. With every iteration, the grasp develops a extra correct illustration of the operational actuality hidden behind its choices.<\/p>\n

The concept turned the muse of Benders\u2019s doctoral thesis, Partitioning in Mathematical Programming<\/em>, accomplished at Utrecht College in 1960 below the supervision of Hans Freudenthal [4, 5]. In 1962, he printed the tactic within the now-classic paper \u201cPartitioning Procedures for Fixing Blended-Variables Programming Issues\u201d [6]. Greater than six a long time later, Benders decomposition stays probably the most influential decomposition strategies in mathematical optimization. It has been prolonged, strengthened, and efficiently utilized to facility location, transportation, supply-chain design, vitality techniques, stochastic programming, scheduling, and lots of different troublesome optimization issues [7].<\/p>\n

Benders decomposition has additionally turn into a staple in my very own operations analysis toolkit, however I need to admit that it took me significantly longer than it ought to have to grasp it correctly. Its central perception is elegant and intuitive, but many studying supplies introduce it by dense notation, excessive factors, twin rays, and prolonged derivations earlier than clearly explaining what the algorithm is making an attempt to perform. In consequence, a method constructed round a remarkably easy dialog between two optimization issues can initially seem much more mysterious than it truly is.<\/p>\n

This sequence of three articles is my try to supply the Benders decomposition tutorial that I might have cherished to have throughout the first years of my PhD. My goal is to make the tactic accessible to anybody fascinated by operations analysis and mathematical optimization, with out sacrificing the mathematical reasoning required to grasp why it really works. We are going to progress from classical optimality cuts, to infeasible subproblems and feasibility cuts, and eventually to logic-based Benders decomposition for combinatorial issues.<\/p>\n

On this first article, we start with essentially the most accessible attainable setting: an issue wherein acquiring a possible resolution is easy, however figuring out the optimum one stays difficult. We are going to first clarify the overall mechanics of Benders decomposition and the roles performed by the grasp downside, the subproblem, and the optimality cuts. We are going to then work by a small toy downside by hand, deriving every minimize step-by-step till the decrease and higher bounds converge to the optimum resolution. Lastly, we are going to apply the identical equipment to the uncapacitated facility location downside and implement the whole algorithm in Python utilizing Pyomo and the open-source HiGHS solver.<\/p>\n

1. The fundamental concept behind Benders decomposition<\/h2>\n

Many optimization issues mix two basically various kinds of choices. The primary are strategic choices that decide the construction of the answer and are sometimes binary or integer. The second are operational choices that turn into a lot simpler to optimize as soon as the strategic selections are recognized.<\/p>\n

Facility location supplies a pure instance. Deciding which services to open is a strategic determination, whereas assigning clients to the chosen services is an operational determination. Benders decomposition separates these two layers as a substitute of fixing them concurrently.<\/p>\n

Think about an optimization downside of the next type:<\/p>\n

min<\/mi>x<\/mi>,<\/mo>y<\/mi><\/mrow><\/msub>\u2061<\/mo>c<\/mi>\u22a4<\/mi><\/msup>x<\/mi>+<\/mo>d<\/mi>\u22a4<\/mi><\/msup>y<\/mi><\/mrow>min_{x,y} quad c^prime x + d^prime y<\/annotation><\/semantics><\/math><\/strong><\/p>\n

topic to<\/p>\n

A<\/mi>x<\/mi>+<\/mo>B<\/mi>y<\/mi>\u2265<\/mo>b<\/mi>,<\/mo>x<\/mi>\u2208<\/mo>X<\/mi>,<\/mo>y<\/mi>\u2265<\/mo>0.<\/mn><\/mrow>Ax + By geq b, qquad x in X, qquad y geq 0.<\/annotation><\/semantics><\/math><\/p>\n

The variables (<\/mo>x<\/mi>)<\/mo><\/mrow>(x)<\/annotation><\/semantics><\/math> symbolize the troublesome strategic choices, whereas (<\/mo>y<\/mi>)<\/mo><\/mrow>(y)<\/annotation><\/semantics><\/math>accommodates the operational choices. If we quickly repair the strategic variables at some worth (x<\/mi>\u203e<\/mo><\/mover>bar{x}<\/annotation><\/semantics><\/math>), the remaining optimization downside turns into:<\/p>\n

Q<\/mi>(<\/mo>x<\/mi>\u203e<\/mo><\/mover>)<\/mo>=<\/mo>min<\/mi>y<\/mi><\/msub>\u2061<\/mo>d<\/mi>\u22a4<\/mi><\/msup>y<\/mi><\/mrow>Q(bar{x}) = min_y quad d^prime y<\/annotation><\/semantics><\/math><\/p>\n

Topic to<\/p>\n

B<\/mi>y<\/mi>\u2265<\/mo>b<\/mi>\u2212<\/mo>A<\/mi>x<\/mi>\u203e<\/mo><\/mover>,<\/mo>y<\/mi>\u2265<\/mo>0<\/mn><\/mrow>By geq b \u2013 Abar{x}, qquad y geq 0<\/annotation><\/semantics><\/math><\/p>\n

The operate Q<\/mi>(<\/mo>x<\/mi>)<\/mo><\/mrow>Q(x)<\/annotation><\/semantics><\/math> represents the perfect operational price related to a strategic determination (x<\/mi>x<\/annotation><\/semantics><\/math>). Subsequently, the unique downside might be seen as:<\/p>\n

min<\/mi>x<\/mi>\u2208<\/mo>X<\/mi><\/mrow><\/msub>\u2061<\/mo>c<\/mi>\u22a4<\/mi><\/msup>x<\/mi>+<\/mo>Q<\/mi>(<\/mo>x<\/mi>)<\/mo>.<\/mi><\/mrow>min_{x in X} quad c^prime x + Q(x).<\/annotation><\/semantics><\/math><\/p>\n

The issue is that the grasp downside doesn’t initially know the operate Q<\/mi>(<\/mo>x<\/mi>)<\/mo><\/mrow>Q(x)<\/annotation><\/semantics><\/math>. Benders decomposition introduces a variable (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>) to approximate it:<\/p>\n

min<\/mi>x<\/mi>,<\/mo>\u03b8<\/mi><\/mrow><\/msub>\u2061<\/mo>c<\/mi>\u22a4<\/mi><\/msup>x<\/mi>+<\/mo>\u03b8<\/mi>.<\/mi><\/mrow>min_{x,theta} quad c^prime x + theta.<\/annotation><\/semantics><\/math><\/p>\n

The grasp and subproblem are then solved iteratively, with every subproblem resolution offering new details about Q<\/mi>(<\/mo>x<\/mi>)<\/mo><\/mrow>Q(x)<\/annotation><\/semantics><\/math>. The subsequent query is the place this data comes from and the way it may be expressed as a sound constraint.<\/p>\n

2. The place do Benders cuts come from?<\/h2>\n

For a set strategic determination (x<\/mi>x<\/annotation><\/semantics><\/math>), the operational subproblem is:<\/p>\n

Q<\/mi>(<\/mo>x<\/mi>)<\/mo>=<\/mo>min<\/mi>y<\/mi><\/msub>\u2061<\/mo>d<\/mi>\u22a4<\/mi><\/msup>y<\/mi><\/mrow>Q(x)=min_y quad d^prime y<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

B<\/mi>y<\/mi>\u2265<\/mo>b<\/mi>\u2212<\/mo>A<\/mi>x<\/mi>,<\/mo>y<\/mi>\u2265<\/mo>0.<\/mn><\/mrow>Bygeq b-Ax, qquad ygeq 0.<\/annotation><\/semantics><\/math><\/p>\n

As a result of it is a linear program, it has the next twin:<\/p>\n

max<\/mi>u<\/mi><\/msub>\u2061<\/mo>(<\/mo>b<\/mi>\u2212<\/mo>A<\/mi>x<\/mi>)<\/mo>\u22a4<\/mi><\/msup>u<\/mi><\/mrow>max_u quad (b-Ax)^prime u<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

B<\/mi>\u22a4<\/mi><\/msup>u<\/mi>\u2264<\/mo>d<\/mi>,<\/mo>u<\/mi>\u2265<\/mo>0.<\/mn><\/mrow>B^prime uleq d, qquad ugeq 0.<\/annotation><\/semantics><\/math><\/p>\n

Each possible twin resolution (u<\/mi>ok<\/mi><\/msup>u^ok<\/annotation><\/semantics><\/math>) supplies a decrease sure on the operational price:<\/p>\n

Q<\/mi>(<\/mo>x<\/mi>)<\/mo>\u2265<\/mo>(<\/mo>b<\/mi>\u2212<\/mo>A<\/mi>x<\/mi>)<\/mo>\u22a4<\/mi><\/msup>u<\/mi>ok<\/mi><\/msup>.<\/mi><\/mrow>Q(x)geq (b-Ax)^prime u^ok.<\/annotation><\/semantics><\/math><\/p>\n

Since (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>) represents the grasp downside\u2019s approximation of Q<\/mi>(<\/mo>x<\/mi>)<\/mo><\/mrow>Q(x)<\/annotation><\/semantics><\/math>, we are able to impose:<\/p>\n

\u03b8<\/mi>\u2265<\/mo>(<\/mo>b<\/mi>\u2212<\/mo>A<\/mi>x<\/mi>)<\/mo>\u22a4<\/mi><\/msup>u<\/mi>ok<\/mi><\/msup>.<\/mi><\/mrow>thetageq (b-Ax)^prime u^ok.<\/annotation><\/semantics><\/math><\/p>\n

This inequality is a Benders optimality minimize<\/strong>. Its key benefit is that it doesn’t solely describe the operational price of the present grasp resolution. It stays legitimate for different values of (x<\/mi>x<\/annotation><\/semantics><\/math>), permitting one subproblem resolve to enhance the grasp\u2019s understanding of a number of attainable strategic choices.<\/p>\n

3. A small instance, solved step-by-step<\/h2>\n

The earlier sections launched the formal construction of Benders decomposition and defined the place optimality cuts come from. Nevertheless, these concepts can nonetheless really feel summary when they’re introduced solely by basic notation. To make the mechanism extra concrete, we are going to now work by a really small instance by hand and comply with the algorithm one iteration at a time.<\/p>\n

The aim of this instance is to not resolve a practical optimization downside. It’s to make the interplay between the grasp downside and the subproblem utterly seen. We are going to see how the grasp begins with a very optimistic estimate, how the subproblem reveals the true operational price of that call, and the way the twin resolution generates a minimize that makes the grasp barely wiser within the subsequent iteration.<\/p>\n

3.1 The toy optimization downside<\/h3>\n

So, contemplate the next small optimization downside:<\/p>\n

min<\/mi>\u2061<\/mo><\/mrow>6<\/mn>x<\/mi>1<\/mn><\/msub>+<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>+<\/mo>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub><\/mrow>min quad 6x_1 + 4x_2 + y_1 + y_2<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>y_1 geq 10 \u2013 8x_1 \u2013 4x_2,<\/annotation><\/semantics><\/math><\/p>\n

y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>y_2 geq 6 \u2013 2x_1 \u2013 6x_2,<\/annotation><\/semantics><\/math><\/p>\n

x<\/mi>1<\/mn><\/msub>,<\/mo>x<\/mi>2<\/mn><\/msub>\u2208<\/mo>0,1<\/mn>,<\/mo>y<\/mi>1<\/mn><\/msub>,<\/mo>y<\/mi>2<\/mn><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>x_1,x_2 in {0,1}, qquad y_1,y_2 geq 0.<\/annotation><\/semantics><\/math><\/p>\n

We are able to interpret (x<\/mi>1<\/mn><\/msub>x_1<\/annotation><\/semantics><\/math>) and (x<\/mi>2<\/mn><\/msub>x_2<\/annotation><\/semantics><\/math>) as two strategic funding choices. Activating the primary possibility prices 6 models, whereas activating the second prices 4 models. The variables (y<\/mi>1<\/mn><\/msub>y_1<\/annotation><\/semantics><\/math>) and (y<\/mi>2<\/mn><\/msub>y_2<\/annotation><\/semantics><\/math>) symbolize the remaining operational necessities after these strategic choices have been made, with every unit carrying a value of 1.<\/p>\n

3.2 The preliminary grasp downside<\/h3>\n

Benders decomposition begins by putting the strategic variables (x<\/mi>1<\/mn><\/msub>x_1<\/annotation><\/semantics><\/math>) and (x<\/mi>2<\/mn><\/msub>x_2<\/annotation><\/semantics><\/math>) within the grasp downside. The operational variables (y<\/mi>1<\/mn><\/msub>y_1<\/annotation><\/semantics><\/math>) and (y<\/mi>2<\/mn><\/msub>y_2<\/annotation><\/semantics><\/math>) are quickly eliminated and changed by the variable (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>), which represents an estimate of their mixed price.<\/p>\n

The preliminary grasp downside is subsequently:<\/p>\n

min<\/mi>\u2061<\/mo><\/mrow>6<\/mn>x<\/mi>1<\/mn><\/msub>+<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>+<\/mo>\u03b8<\/mi><\/mrow>min quad 6x_1 + 4x_2 + theta<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

\u03b8<\/mi>\u2265<\/mo>0<\/mn>,<\/mo><\/mrow>theta geq 0,<\/annotation><\/semantics><\/math><\/p>\n

x<\/mi>1<\/mn><\/msub>,<\/mo>x<\/mi>2<\/mn><\/msub>\u2208<\/mo>0,1.<\/mn><\/mrow>x_1,x_2 in {0,1}.<\/annotation><\/semantics><\/math><\/p>\n

At this stage, the grasp has not but acquired any Benders cuts. It solely is aware of that the operational price can’t be adverse. Consequently, its optimum resolution is:<\/p>\n

x<\/mi>\u203e<\/mo><\/mover>1<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo>x<\/mi>\u203e<\/mo><\/mover>2<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo>\u03b8<\/mi>=<\/mo>0.<\/mn><\/mrow>bar{x}_1=0, qquad bar{x}_2=0, qquad theta=0.<\/annotation><\/semantics><\/math><\/p>\n

The grasp subsequently proposes making no strategic funding and assumes that the operational price will even be zero. Its goal worth is L<\/mi>B<\/mi>=<\/mo>0.<\/mn><\/mrow>LB=0.<\/annotation><\/semantics><\/math><\/p>\n

This worth supplies a decrease sure on the optimum goal as a result of the grasp is presently underestimating the operational price. The answer shouldn’t be but legitimate for the unique downside, for the reason that operational necessities represented by (y<\/mi>1<\/mn><\/msub>y_1<\/annotation><\/semantics><\/math>) and (y<\/mi>2<\/mn><\/msub>y_2<\/annotation><\/semantics><\/math>) haven’t been evaluated. The subsequent step is subsequently to ship the choice (x<\/mi>\u203e<\/mo><\/mover>=<\/mo>(<\/mo>0,0<\/mn>)<\/mo><\/mrow>bar{x}=(0,0)<\/annotation><\/semantics><\/math>) to the subproblem and decide its true operational penalties.<\/p>\n

3.3 Evaluating the grasp determination<\/h3>\n

The grasp downside has proposed the strategic determination:<\/p>\n

x<\/mi>\u203e<\/mo><\/mover>1<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo>x<\/mi>\u203e<\/mo><\/mover>2<\/mn><\/msub>=<\/mo>0.<\/mn><\/mrow>bar{x}_1=0, qquad bar{x}_2=0.<\/annotation><\/semantics><\/math><\/p>\n

The subproblem is obtained by fixing the strategic variables (x<\/mi>1<\/mn><\/msub>x_1<\/annotation><\/semantics><\/math>) and (x<\/mi>2<\/mn><\/msub>x_2<\/annotation><\/semantics><\/math>) at these values and optimizing solely the operational variables (y<\/mi>1<\/mn><\/msub>y_1<\/annotation><\/semantics><\/math>) and (y<\/mi>2<\/mn><\/msub>y_2<\/annotation><\/semantics><\/math>).<\/p>\n

Recall the target operate of the unique downside:<\/p>\n

min<\/mi>\u2061<\/mo><\/mrow>6<\/mn>x<\/mi>1<\/mn><\/msub>+<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>+<\/mo>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>min quad 6x_1+4x_2+y_1+y_2.<\/annotation><\/semantics><\/math><\/p>\n

The phrases (6<\/mn>x<\/mi>1<\/mn><\/msub>+<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub><\/mrow>6x_1+4x_2<\/annotation><\/semantics><\/math>) symbolize the strategic price and are already accounted for within the grasp downside. Subsequently, the subproblem solely wants to attenuate the operational price:<\/p>\n

Q<\/mi>(<\/mo>x<\/mi>\u203e<\/mo><\/mover>)<\/mo>=<\/mo>min<\/mi>\u2061<\/mo><\/mrow>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>Q(bar{x})=min quad y_1+y_2.<\/annotation><\/semantics><\/math><\/p>\n

We now substitute the grasp resolution (x<\/mi>\u203e<\/mo><\/mover>1<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>bar{x}_1=0<\/annotation><\/semantics><\/math>) and (x<\/mi>\u203e<\/mo><\/mover>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>bar{x}_2=0<\/annotation><\/semantics><\/math>) into every operational constraint. The primary constraint turns into:<\/p>\n

y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>(<\/mo>0<\/mn>)<\/mo>\u2212<\/mo>4<\/mn>(<\/mo>0<\/mn>)<\/mo>=<\/mo>10.<\/mn><\/mrow>y_1geq 10-8(0)-4(0)=10.<\/annotation><\/semantics><\/math><\/p>\n

The second constraint turns into:<\/p>\n

y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>(<\/mo>0<\/mn>)<\/mo>\u2212<\/mo>6<\/mn>(<\/mo>0<\/mn>)<\/mo>=<\/mo>6.<\/mn><\/mrow>y_2geq 6-2(0)-6(0)=6.<\/annotation><\/semantics><\/math><\/p>\n

The entire subproblem is subsequently:<\/p>\n

Q<\/mi>(<\/mo>0,0<\/mn>)<\/mo>=<\/mo>min<\/mi>\u2061<\/mo><\/mrow>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub><\/mrow>Q(0,0)=min quad y_1+y_2<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>,<\/mo><\/mrow>y_1geq 10,<\/annotation><\/semantics><\/math><\/p>\n

y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>,<\/mo><\/mrow>y_2geq 6,<\/annotation><\/semantics><\/math><\/p>\n

y<\/mi>1<\/mn><\/msub>,<\/mo>y<\/mi>2<\/mn><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>y_1,y_2geq 0.<\/annotation><\/semantics><\/math><\/p>\n

As a result of each variables have constructive coefficients within the goal operate, the subproblem chooses the smallest possible values:<\/p>\n

y<\/mi>1<\/mn><\/msub>=<\/mo>10<\/mn>,<\/mo>y<\/mi>2<\/mn><\/msub>=<\/mo>6.<\/mn><\/mrow>y_1=10, qquad y_2=6.<\/annotation><\/semantics><\/math><\/p>\n

The operational price related to the grasp determination is subsequently:<\/p>\n

Q<\/mi>(<\/mo>0,0<\/mn>)<\/mo>=<\/mo>10<\/mn>+<\/mo>6<\/mn>=<\/mo>16.<\/mn><\/mrow>Q(0,0)=10+6=16.<\/annotation><\/semantics><\/math><\/p>\n

The strategic price of selecting (<\/mo>x<\/mi>1<\/mn><\/msub>=<\/mo>x<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>(x_1=x_2=0<\/annotation><\/semantics><\/math>) is zero, so the entire price of this possible resolution to the unique downside is:<\/p>\n

6<\/mn>(<\/mo>0<\/mn>)<\/mo>+<\/mo>4<\/mn>(<\/mo>0<\/mn>)<\/mo>+<\/mo>16<\/mn>=<\/mo>16.<\/mn><\/mrow>6(0)+4(0)+16=16.<\/annotation><\/semantics><\/math><\/p>\n

This offers us an higher sure of (16), whereas the grasp goal supplies a decrease sure of (0):<\/p>\n

L<\/mi>B<\/mi>=<\/mo>0<\/mn>,<\/mo>U<\/mi>B<\/mi>=<\/mo>16.<\/mn><\/mrow>LB=0, qquad UB=16.<\/annotation><\/semantics><\/math><\/p>\n

3.4 Developing the twin subproblem<\/h3>\n

The subproblem tells us the operational price related to the present grasp determination. Nevertheless, to generate a Benders minimize, we want greater than the worth (Q<\/mi>(<\/mo>0,0<\/mn>)<\/mo>=<\/mo>16<\/mn><\/mrow>Q(0,0)=16<\/annotation><\/semantics><\/math>). We’d like an expression that is still legitimate when the grasp later considers completely different values of (x<\/mi>1<\/mn><\/msub>x_1<\/annotation><\/semantics><\/math>) and (x<\/mi>2<\/mn><\/msub>x_2<\/annotation><\/semantics><\/math>). This expression comes from the twin of the subproblem.<\/p>\n

Earlier than substituting the present grasp resolution, allow us to write the subproblem utilizing the generic strategic variables (x<\/mi>1<\/mn><\/msub>x_1<\/annotation><\/semantics><\/math>) and (x<\/mi>2<\/mn><\/msub>x_2<\/annotation><\/semantics><\/math>):<\/p>\n

Q<\/mi>(<\/mo>x<\/mi>)<\/mo>=<\/mo>min<\/mi>\u2061<\/mo><\/mrow>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub><\/mrow>Q(x)=min quad y_1+y_2<\/annotation><\/semantics><\/math><\/p>\n

topic to<\/p>\n

y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>y_1geq 10-8x_1-4x_2,<\/annotation><\/semantics><\/math><\/p>\n

y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>y_2geq 6-2x_1-6x_2,<\/annotation><\/semantics><\/math><\/p>\n

y<\/mi>1<\/mn><\/msub>,<\/mo>y<\/mi>2<\/mn><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>y_1,y_2geq 0.<\/annotation><\/semantics><\/math><\/p>\n

To assemble the twin, we use two fundamental guidelines:<\/p>\n

    \n
  1. Every constraint within the primal subproblem creates one twin variable.<\/li>\n
  2. Every variable within the primal subproblem creates one constraint within the twin.<\/li>\n<\/ol>\n

    The primary primal constraint receives the twin variable (u<\/mi>1<\/mn><\/msub>u_1<\/annotation><\/semantics><\/math>), whereas the second receives (u<\/mi>2<\/mn><\/msub>u_2<\/annotation><\/semantics><\/math>):<\/p>\n

    u<\/mi>1<\/mn><\/msub>\u27f7<\/mo>y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>u_1 longleftrightarrow y_1geq 10-8x_1-4x_2,<\/annotation><\/semantics><\/math><\/p>\n

    u<\/mi>2<\/mn><\/msub>\u27f7<\/mo>y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>u_2 longleftrightarrow y_2geq 6-2x_1-6x_2.<\/annotation><\/semantics><\/math><\/p>\n

    As a result of the primal is a minimization downside and its constraints use the greater-than-or-equal-to route, each twin variables have to be nonnegative:<\/p>\n

    u<\/mi>1<\/mn><\/msub>,<\/mo>u<\/mi>2<\/mn><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>u_1,u_2geq 0.<\/annotation><\/semantics><\/math><\/p>\n

    The twin goal is constructed by multiplying the right-hand aspect of every primal constraint by its corresponding twin variable. Subsequently, the twin goal is:<\/p>\n

    max<\/mi>\u2061<\/mo><\/mrow>(<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>1<\/mn><\/msub>+<\/mo>(<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>max quad (10-8x_1-4x_2)u_1 + (6-2x_1-6x_2)u_2.<\/annotation><\/semantics><\/math><\/p>\n

    We now assemble the twin constraints. There’s one twin constraint for every primal variable.<\/p>\n

    The variable (y<\/mi>1<\/mn><\/msub>y_1<\/annotation><\/semantics><\/math>) seems solely within the first primal constraint, with a coefficient of 1. Its coefficient within the primal goal can also be 1. Subsequently, the corresponding twin constraint is:<\/p>\n

    u<\/mi>1<\/mn><\/msub>\u2264<\/mo>1.<\/mn><\/mrow>u_1leq 1.<\/annotation><\/semantics><\/math><\/p>\n

    Equally, (y<\/mi>2<\/mn><\/msub>y_2<\/annotation><\/semantics><\/math>) seems solely within the second primal constraint, additionally with a coefficient of 1, and its goal coefficient is 1. Its twin constraint is subsequently:<\/p>\n

    u<\/mi>2<\/mn><\/msub>\u2264<\/mo>1.<\/mn><\/mrow>u_2leq 1.<\/annotation><\/semantics><\/math><\/p>\n

    Combining these parts, the twin of the overall subproblem is:<\/p>\n

    max<\/mi>\u2061<\/mo><\/mrow>(<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>1<\/mn><\/msub>+<\/mo>(<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>2<\/mn><\/msub><\/mrow>max quad (10-8x_1-4x_2)u_1 + (6-2x_1-6x_2)u_2<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    0<\/mn>\u2264<\/mo>u<\/mi>1<\/mn><\/msub>\u2264<\/mo>1<\/mn>,<\/mo><\/mrow>0leq u_1leq 1,<\/annotation><\/semantics><\/math><\/p>\n

    0<\/mn>\u2264<\/mo>u<\/mi>2<\/mn><\/msub>\u2264<\/mo>1.<\/mn><\/mrow>0leq u_2leq 1.<\/annotation><\/semantics><\/math><\/p>\n

    We are able to now consider this twin on the present grasp resolution (x<\/mi>\u203e<\/mo><\/mover>1<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>bar{x}_1=0<\/annotation><\/semantics><\/math>) and (x<\/mi>\u203e<\/mo><\/mover>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>bar{x}_2=0<\/annotation><\/semantics><\/math>). Substituting these values into the target offers:<\/p>\n

    max<\/mi>\u2061<\/mo><\/mrow>10<\/mn>u<\/mi>1<\/mn><\/msub>+<\/mo>6<\/mn>u<\/mi>2<\/mn><\/msub><\/mrow>max quad 10u_1+6u_2<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    0<\/mn>\u2264<\/mo>u<\/mi>1<\/mn><\/msub>\u2264<\/mo>1<\/mn>,<\/mo><\/mrow>0leq u_1leq 1,<\/annotation><\/semantics><\/math><\/p>\n

    0<\/mn>\u2264<\/mo>u<\/mi>2<\/mn><\/msub>\u2264<\/mo>1.<\/mn><\/mrow>0leq u_2leq 1.<\/annotation><\/semantics><\/math><\/p>\n

    Each coefficients within the goal are constructive, so the target is maximized by setting each twin variables to their largest possible values:<\/p>\n

    u<\/mi>1<\/mn>=<\/mo><\/msubsup>1<\/mn>,<\/mo>u<\/mi>2<\/mn>=<\/mo><\/msubsup>1.<\/mn><\/mrow>u_1^=1, qquad u_2^=1.<\/annotation><\/semantics><\/math><\/p>\n

    The optimum twin goal worth is subsequently:<\/p>\n

    10<\/mn>(<\/mo>1<\/mn>)<\/mo>+<\/mo>6<\/mn>(<\/mo>1<\/mn>)<\/mo>=<\/mo>16.<\/mn><\/mrow>10(1)+6(1)=16.<\/annotation><\/semantics><\/math><\/p>\n

    This matches the optimum worth of the primal subproblem, Q(0,0)=16. This equality is a consequence of sturdy duality. As a result of the primal and twin subproblems are each possible linear packages, their optimum goal values are equal. The twin resolution (u<\/mi>1<\/mn><\/msub>=<\/mo>u<\/mi>2<\/mn><\/msub>=<\/mo>1<\/mn><\/mrow>u_1 =u_2 =1<\/annotation><\/semantics><\/math>) will now permit us to remodel the operational data obtained at (x<\/mi>=<\/mo>(<\/mo>0,0<\/mn>)<\/mo><\/mrow>x=(0,0)<\/annotation><\/semantics><\/math>) right into a Benders minimize that is still legitimate for different strategic choices.<\/p>\n

    3.5 Producing the primary Benders minimize<\/h3>\n

    The optimum twin resolution obtained for the present grasp determination is, u<\/mi>1<\/mn><\/msub>=<\/mo>1<\/mn>,<\/mo>u<\/mi>2<\/mn><\/msub>=<\/mo>1.<\/mn><\/mrow>u_1=1, u_2=1.<\/annotation><\/semantics><\/math>Recall that the target of the overall twin subproblem is:<\/p>\n

    (<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>1<\/mn><\/msub>+<\/mo>(<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>u<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>(10-8x_1-4x_2)u_1+(6-2x_1-6x_2)u_2.<\/annotation><\/semantics><\/math><\/p>\n

    To generate the Benders minimize, we substitute the optimum twin values into this expression:<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>(<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>(<\/mo>1<\/mn>)<\/mo>+<\/mo>(<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>6<\/mn>x<\/mi>2<\/mn><\/msub>)<\/mo>(<\/mo>1<\/mn>)<\/mo>.<\/mi><\/mrow>theta geq (10-8x_1-4x_2)(1)+(6-2x_1-6x_2)(1).<\/annotation><\/semantics><\/math><\/p>\n

    After accumulating phrases, we receive:<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>16<\/mn>\u2212<\/mo>10<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>10<\/mn>x<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>theta geq 16-10x_1-10x_2.<\/annotation><\/semantics><\/math><\/p>\n

    This inequality is the primary Benders optimality minimize. On the present resolution (x<\/mi>1<\/mn><\/msub>=<\/mo>x<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>x_1=x_2=0<\/annotation><\/semantics><\/math>), it forces (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>) to be no less than 16, which is strictly the operational price discovered by the subproblem. Nevertheless, the minimize additionally describes how this decrease sure adjustments when both strategic possibility is chosen.<\/p>\n

    We now add the minimize to the grasp downside:<\/p>\n

    min<\/mi>\u2061<\/mo><\/mrow>6<\/mn>x<\/mi>1<\/mn><\/msub>+<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>+<\/mo>\u03b8<\/mi><\/mrow>min quad 6x_1+4x_2+theta<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>0<\/mn>,<\/mo><\/mrow>thetageq 0,<\/annotation><\/semantics><\/math><\/p>\n

    \u03b8<\/mi>\u2265<\/mo>16<\/mn>\u2212<\/mo>10<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>10<\/mn>x<\/mi>2<\/mn><\/msub>,<\/mo><\/mrow>thetageq 16-10x_1-10x_2,<\/annotation><\/semantics><\/math><\/p>\n

    x<\/mi>1<\/mn><\/msub>,<\/mo>x<\/mi>2<\/mn><\/msub>\u2208<\/mo>0,1.<\/mn><\/mrow>x_1,x_2in{0,1}.<\/annotation><\/semantics><\/math><\/p>\n

    The grasp can not select (x<\/mi>1<\/mn><\/msub>=<\/mo>x<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>x_1=x_2=0<\/annotation><\/semantics><\/math>) whereas pretending that the operational price is zero. If it makes no funding, the brand new minimize requires (\u03b8<\/mi>\u2265<\/mo>16<\/mn><\/mrow>thetageq16<\/annotation><\/semantics><\/math>), giving a complete estimated price of 16.<\/p>\n

    If it selects solely the second possibility, the minimize offers:<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>16<\/mn>\u2212<\/mo>10<\/mn>(<\/mo>0<\/mn>)<\/mo>\u2212<\/mo>10<\/mn>(<\/mo>1<\/mn>)<\/mo>=<\/mo>6.<\/mn><\/mrow>thetageq 16-10(0)-10(1)=6.<\/annotation><\/semantics><\/math><\/p>\n

    The corresponding grasp goal worth is:<\/p>\n

    6<\/mn>(<\/mo>0<\/mn>)<\/mo>+<\/mo>4<\/mn>(<\/mo>1<\/mn>)<\/mo>+<\/mo>6<\/mn>=<\/mo>10.<\/mn><\/mrow>6(0)+4(1)+6=10.<\/annotation><\/semantics><\/math><\/p>\n

    The up to date grasp subsequently strikes away from the unique determination and proposes:<\/p>\n

    x<\/mi>\u203e<\/mo><\/mover>1<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo>x<\/mi>\u203e<\/mo><\/mover>2<\/mn><\/msub>=<\/mo>1<\/mn>,<\/mo>\u03b8<\/mi>=<\/mo>6.<\/mn><\/mrow>bar{x}_1=0, qquad bar{x}_2=1, qquad theta=6.<\/annotation><\/semantics><\/math><\/p>\n

    Its new goal worth is:<\/p>\n

    L<\/mi>B<\/mi>=<\/mo>10.<\/mn><\/mrow>LB=10.<\/annotation><\/semantics><\/math><\/p>\n

    The grasp has now discovered that avoiding strategic funding creates a considerable operational burden. The subsequent step is to ship the brand new determination (x<\/mi>\u203e<\/mo><\/mover>=<\/mo>(<\/mo>0,1<\/mn>)<\/mo><\/mrow>bar{x}=(0,1)<\/annotation><\/semantics><\/math>) to the subproblem and confirm whether or not the estimated operational price (\u03b8<\/mi>=<\/mo>6<\/mn><\/mrow>theta=6<\/annotation><\/semantics><\/math>) is correct.<\/p>\n

    3.6 The second iteration and convergence<\/h3>\n

    After including the primary optimality minimize, the grasp proposes the answer, with an goal worth of (10), which turns into the brand new decrease sure L<\/mi>B<\/mi>=<\/mo>10.<\/mn><\/mrow>LB=10.<\/annotation><\/semantics><\/math><\/p>\n

    It is very important spotlight, that the up to date grasp is definitely detached between (x<\/mi>=<\/mo>(<\/mo>0,1<\/mn>)<\/mo><\/mrow>x=(0,1)<\/annotation><\/semantics><\/math> with (\u03b8<\/mi>=<\/mo>6<\/mn><\/mrow>theta = 6<\/annotation><\/semantics><\/math>)) and (x<\/mi>=<\/mo>(<\/mo>1,1<\/mn>)<\/mo><\/mrow>x=(1,1)<\/annotation><\/semantics><\/math> with (\u03b8<\/mi>=<\/mo>0<\/mn><\/mrow>theta = 0<\/annotation><\/semantics><\/math>)), since each produce an goal worth of (10). The answer chosen might subsequently depend upon the solver\u2019s tie-breaking guidelines. For this rationalization, we are going to proceed with (x<\/mi>=<\/mo>(<\/mo>0,1<\/mn>)<\/mo><\/mrow>x=(0,1)<\/annotation><\/semantics><\/math>).<\/p>\n

    To guage this determination, we as soon as once more repair the strategic variables within the authentic operational constraints of the subproblem. The primary constraint turns into:<\/p>\n

    y<\/mi>1<\/mn><\/msub>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>(<\/mo>0<\/mn>)<\/mo>\u2212<\/mo>4<\/mn>(<\/mo>1<\/mn>)<\/mo>=<\/mo>6<\/mn>,<\/mo><\/mrow>y_1geq 10-8(0)-4(1)=6,<\/annotation><\/semantics><\/math><\/p>\n

    whereas the second turns into:<\/p>\n

    y<\/mi>2<\/mn><\/msub>\u2265<\/mo>6<\/mn>\u2212<\/mo>2<\/mn>(<\/mo>0<\/mn>)<\/mo>\u2212<\/mo>6<\/mn>(<\/mo>1<\/mn>)<\/mo>=<\/mo>0.<\/mn><\/mrow>y_2geq 6-2(0)-6(1)=0.<\/annotation><\/semantics><\/math><\/p>\n

    The ensuing subproblem is then:<\/p>\n

    Q<\/mi>(<\/mo>0,1<\/mn>)<\/mo>=<\/mo>min<\/mi>\u2061<\/mo><\/mrow>y<\/mi>1<\/mn><\/msub>+<\/mo>y<\/mi>2<\/mn><\/msub><\/mrow>Q(0,1)=min quad y_1+y_2<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    y<\/mi>1<\/mn><\/msub>\u2265<\/mo>6<\/mn>,<\/mo><\/mrow>y_1geq 6,<\/annotation><\/semantics><\/math><\/p>\n

    y<\/mi>2<\/mn><\/msub>\u2265<\/mo>0<\/mn>,<\/mo><\/mrow>y_2geq 0,<\/annotation><\/semantics><\/math><\/p>\n

    y<\/mi>1<\/mn><\/msub>,<\/mo>y<\/mi>2<\/mn><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>y_1,y_2geq 0.<\/annotation><\/semantics><\/math><\/p>\n

    The optimum operational resolution is subsequently:<\/p>\n

    y<\/mi>1<\/mn><\/msub>=<\/mo>6<\/mn>,<\/mo>y<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo><\/mrow>y_1=6, qquad y_2=0,<\/annotation><\/semantics><\/math><\/p>\n

    with an operational price of, Q<\/mi>(<\/mo>0,1<\/mn>)<\/mo>=<\/mo>6.<\/mn><\/mrow>Q(0,1)=6.<\/annotation><\/semantics><\/math> That is precisely the worth predicted by the grasp by (\u03b8<\/mi>=<\/mo>6<\/mn><\/mrow>theta=6<\/annotation><\/semantics><\/math>). Including the strategic price offers a complete possible price of:<\/p>\n

    6<\/mn>(<\/mo>0<\/mn>)<\/mo>+<\/mo>4<\/mn>(<\/mo>1<\/mn>)<\/mo>+<\/mo>6<\/mn>=<\/mo>10.<\/mn><\/mrow>6(0)+4(1)+6=10.<\/annotation><\/semantics><\/math><\/p>\n

    This resolution improves the earlier higher sure of (16), so, U<\/mi>B<\/mi>=<\/mo>10.<\/mn><\/mrow>UB=10.<\/annotation><\/semantics><\/math>We now have:<\/p>\n

    L<\/mi>B<\/mi>=<\/mo>10<\/mn>,<\/mo>U<\/mi>B<\/mi>=<\/mo>10.<\/mn><\/mrow>LB=10, qquad UB=10.<\/annotation><\/semantics><\/math><\/p>\n

    The decrease and higher bounds coincide, which proves that the present resolution (x<\/mi>1<\/mn><\/msub>=<\/mo>1<\/mn>,<\/mo>x<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn>,<\/mo>y<\/mi>1<\/mn><\/msub>=<\/mo>6<\/mn>,<\/mo>y<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>x_1 = 1, x_2=0,y_1=6,y_2=0<\/annotation><\/semantics><\/math>) is perfect. The grasp can not discover a resolution costing lower than (10), whereas the subproblem has confirmed {that a} possible resolution with price (10) exists. Benders decomposition has subsequently converged.<\/p>\n

    For the sake of completeness, the twin subproblem at (x<\/mi>=<\/mo>(<\/mo>0,1<\/mn>)<\/mo><\/mrow>x=(0,1)<\/annotation><\/semantics><\/math>) is:<\/p>\n

    max<\/mi>\u2061<\/mo><\/mrow>6<\/mn>u<\/mi>1<\/mn><\/msub><\/mrow>max quad 6u_1<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    0<\/mn>\u2264<\/mo>u<\/mi>1<\/mn><\/msub>\u2264<\/mo>1<\/mn>,<\/mo>0<\/mn>\u2264<\/mo>u<\/mi>2<\/mn><\/msub>\u2264<\/mo>1.<\/mn><\/mrow>0leq u_1leq 1, qquad 0leq u_2leq 1.<\/annotation><\/semantics><\/math><\/p>\n

    One optimum twin resolution is (u<\/mi>1<\/mn><\/msub>=<\/mo>1<\/mn><\/mrow>u_1=1<\/annotation><\/semantics><\/math>) and (<\/em>u<\/mi>2<\/mn><\/msub>=<\/mo>0<\/mn><\/mrow>u_2=0<\/annotation><\/semantics><\/math>), which might generate the extra minimize:<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>10<\/mn>\u2212<\/mo>8<\/mn>x<\/mi>1<\/mn><\/msub>\u2212<\/mo>4<\/mn>x<\/mi>2<\/mn><\/msub>.<\/mi><\/mrow>thetageq 10-8x_1-4x_2.<\/annotation><\/semantics><\/math><\/p>\n

    Nevertheless, this minimize shouldn’t be required to show optimality as a result of the decrease and higher bounds have already converged.<\/p>\n

    4. Benders decomposition for the uncapacitated facility location downside<\/h2>\n

    Now that we perceive how Benders optimality cuts are generated, we are able to apply the equipment to one of many quintessential issues in operations analysis: the uncapacitated facility location downside<\/strong>, or UFL.<\/p>\n

    Facility location issues seem each time a corporation should resolve the place to ascertain assets that may serve geographically distributed demand. Typical functions embrace finding warehouses, distribution facilities, hospitals, emergency providers, knowledge facilities, and charging stations. The strategic determination is the place to open the services, whereas the operational determination is how clients ought to be assigned to the chosen areas.<\/p>\n

    The uncapacitated model assumes that any open facility can serve any variety of clients. This makes it an particularly handy introduction to Benders decomposition as a result of, supplied that no less than one facility is opened and each buyer might be served by each facility, the task subproblem is at all times possible. <\/p>\n

    4.1 The uncapacitated facility location mannequin<\/h3>\n

    Let (I<\/mi>I<\/annotation><\/semantics><\/math>) denote the set of candidate services and (J<\/mi>J<\/annotation><\/semantics><\/math>) the set of consumers. Opening facility (i<\/mi>i<\/annotation><\/semantics><\/math>) incurs a set price (f<\/mi>i<\/mi><\/msub>f_i<\/annotation><\/semantics><\/math>), whereas assigning buyer (j<\/mi>j<\/annotation><\/semantics><\/math>) to facility (i<\/mi>i<\/annotation><\/semantics><\/math>) incurs a service price (q<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>q_{ij}<\/annotation><\/semantics><\/math>).<\/p>\n

    We outline the strategic variables:<\/p>\n

    x<\/mi>i<\/mi><\/msub>=<\/mo>1<\/mn>\u00a0if\u00a0facility\u00a0<\/mtext>i<\/mi>\u00a0is\u00a0opened,\u00a0and\u00a0<\/mtext>0<\/mn>\u00a0in any other case<\/mtext>.<\/mi><\/mrow>x_i = 1 textual content{ if facility } i textual content{ is opened, and } 0 textual content{ in any other case}.<\/annotation><\/semantics><\/math><\/p>\n

    The operational variables are:<\/p>\n

    y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>=<\/mo>the\u00a0fraction\u00a0of\u00a0buyer\u00a0<\/mtext>j<\/mi>\u00a0served\u00a0by\u00a0facility\u00a0<\/mtext>i<\/mi>.<\/mi><\/mrow>y_{ij} = textual content{the fraction of buyer } j textual content{ served by facility } i.<\/annotation><\/semantics><\/math><\/p>\n

    The entire, or monolithic, formulation is then:<\/p>\n

    min<\/mi>\u2061<\/mo><\/mrow>\u2211<\/mo>i<\/mi><\/msub>f<\/mi>i<\/mi><\/msub>x<\/mi>i<\/mi><\/msub>+<\/mo>\u2211<\/mo>i<\/mi><\/msub>\u2211<\/mo>j<\/mi><\/msub>q<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub><\/mrow>min quad sum_i f_i x_i + sum_i sum_j q_{ij}y_{ij}<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    \u2211<\/mo>i<\/mi><\/msub>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>=<\/mo>1<\/mn>\u2200<\/mi>j<\/mi>,<\/mo><\/mrow>sum_i y_{ij}=1 qquad forall j,<\/annotation><\/semantics><\/math><\/p>\n

    y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2264<\/mo>x<\/mi>i<\/mi><\/msub>\u2200<\/mi>i<\/mi>,<\/mo>j<\/mi>,<\/mo><\/mrow>y_{ij}leq x_i qquad forall i,j,<\/annotation><\/semantics><\/math><\/p>\n

    \u2211<\/mo>i<\/mi><\/msub>x<\/mi>i<\/mi><\/msub>\u2265<\/mo>1<\/mn>,<\/mo><\/mrow>sum_i x_igeq 1,<\/annotation><\/semantics><\/math><\/p>\n

    x<\/mi>i<\/mi><\/msub>\u2208<\/mo>0,1<\/mn>,<\/mo>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>x_iin{0,1}, qquad y_{ij}geq 0.<\/annotation><\/semantics><\/math><\/p>\n

    The primary constraint requires each buyer to be totally assigned. The second prevents clients from being assigned to closed services, the third constraints, forces to open no less than one facility. Though the task variables are steady, the construction of the issue ensures that an optimum resolution assigns every buyer to one of many least expensive open services.<\/p>\n

    4.2 The grasp downside<\/h3>\n

    Within the Benders decomposition, the facility-opening variables stay within the grasp downside. The task variables are eliminated and their price is represented by (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>):<\/p>\n

    min<\/mi>\u2061<\/mo><\/mrow>\u2211<\/mo>i<\/mi><\/msub>f<\/mi>i<\/mi><\/msub>x<\/mi>i<\/mi><\/msub>+<\/mo>\u03b8<\/mi><\/mrow>min quad sum_i f_i x_i+theta<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    \u2211<\/mo>i<\/mi><\/msub>x<\/mi>i<\/mi><\/msub>\u2265<\/mo>1<\/mn>,<\/mo><\/mrow>sum_i x_igeq 1,<\/annotation><\/semantics><\/math><\/p>\n

    x<\/mi>i<\/mi><\/msub>\u2208<\/mo>0,1<\/mn>,<\/mo>\u03b8<\/mi>\u2265<\/mo>0<\/mn>,<\/mo><\/mrow>x_iin{0,1}, qquad thetageq 0,<\/annotation><\/semantics><\/math><\/p>\n

    Please discover that the constraints above, can be joined along with the Benders cuts generated throughout the completely different iterations of the Benders algorithm. The grasp subsequently decides which services to open whereas regularly studying the ensuing task price.<\/p>\n

    4.3 The task subproblem<\/h3>\n

    As soon as the grasp produces a facility-opening determination (x<\/mi>\u203e<\/mo><\/mover>bar{x}<\/annotation><\/semantics><\/math>), we repair these values and resolve the operational task downside:<\/p>\n

    min<\/mi>\u2061<\/mo><\/mrow>\u2211<\/mo>i<\/mi><\/msub>\u2211<\/mo>j<\/mi><\/msub>q<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub><\/mrow>min quad sum_i sum_j q_{ij}y_{ij}<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    \u2211<\/mo>i<\/mi><\/msub>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>=<\/mo>1<\/mn>\u2200<\/mi>j<\/mi>,<\/mo><\/mrow>sum_i y_{ij}=1 qquad forall j,<\/annotation><\/semantics><\/math><\/p>\n

    y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2264<\/mo>x<\/mi>\u203e<\/mo><\/mover>i<\/mi><\/msub>\u2200<\/mi>i<\/mi>,<\/mo>j<\/mi>,<\/mo><\/mrow>y_{ij}leq bar{x}_i qquad forall i,j,<\/annotation><\/semantics><\/math><\/p>\n

    y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2265<\/mo>0.<\/mn><\/mrow>y_{ij}geq 0.<\/annotation><\/semantics><\/math><\/p>\n

    4.4 The twin subproblem and optimality minimize<\/h3>\n

    To generate a Benders minimize, we assemble the twin of the task subproblem. Let (\u03b1<\/mi>j<\/mi><\/msub>alpha_j<\/annotation><\/semantics><\/math>) be the twin variable related to the task equality for buyer (j<\/mi>j<\/annotation><\/semantics><\/math>). Because the corresponding primal constraint is an equality, (\u03b1<\/mi>j<\/mi><\/msub>alpha_j<\/annotation><\/semantics><\/math>) is unrestricted in signal.<\/p>\n

    We rewrite the linking constraint as:<\/p>\n

    \u2212<\/mo>y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2265<\/mo>\u2212<\/mo>x<\/mi>\u203e<\/mo><\/mover>i<\/mi><\/msub><\/mrow>-y_{ij}geq-bar{x}_i<\/annotation><\/semantics><\/math><\/p>\n

    and affiliate it with a nonnegative twin variable (\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>beta_{ij}<\/annotation><\/semantics><\/math>).<\/p>\n

    The twin subproblem is then:<\/p>\n

    max<\/mi>\u2061<\/mo><\/mrow>\u2211<\/mo>j<\/mi><\/msub>\u03b1<\/mi>j<\/mi><\/msub>\u2212<\/mo>\u2211<\/mo>i<\/mi><\/msub>\u2211<\/mo>j<\/mi><\/msub>x<\/mi>\u203e<\/mo><\/mover>i<\/mi><\/msub>\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub><\/mrow>max quad sum_j alpha_j \u2013 sum_i sum_j bar{x}_ibeta_{ij}<\/annotation><\/semantics><\/math><\/p>\n

    topic to<\/p>\n

    \u03b1<\/mi>j<\/mi><\/msub>\u2212<\/mo>\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2264<\/mo>q<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2200<\/mi>i<\/mi>,<\/mo>j<\/mi>,<\/mo><\/mrow>alpha_j-beta_{ij}leq q_{ij} qquad forall i,j,<\/annotation><\/semantics><\/math><\/p>\n

    \u03b2<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>\u2265<\/mo>0<\/mn>,<\/mo>\u03b1<\/mi>j<\/mi><\/msub>\u00a0unrestricted<\/mtext>.<\/mi><\/mrow>beta_{ij}geq 0, qquad alpha_j textual content{ unrestricted}.<\/annotation><\/semantics><\/math><\/p>\n

    Suppose that fixing the twin produces the optimum values (\u03b1<\/mi>j<\/mi>ok<\/mi><\/msubsup>alpha_j^ok<\/annotation><\/semantics><\/math>) and (\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow>ok<\/mi><\/msubsup>beta_{ij}^ok<\/annotation><\/semantics><\/math>). The corresponding Benders optimality minimize is then:<\/p>\n

    \u03b8<\/mi>\u2265<\/mo>\u2211<\/mo>j<\/mi><\/msub>\u03b1<\/mi>j<\/mi>ok<\/mi><\/msubsup>\u2212<\/mo>\u2211<\/mo>i<\/mi><\/msub>\u2211<\/mo>j<\/mi><\/msub>\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow>ok<\/mi><\/msubsup>x<\/mi>i<\/mi><\/msub><\/mrow>theta geq sum_j alpha_j^ok \u2013 sum_i sum_j beta_{ij}^ok x_i<\/annotation><\/semantics><\/math><\/p>\n

    This minimize offers the grasp a brand new decrease sure on the task price. The grasp is then solved once more, a brand new facility configuration is evaluated, and extra cuts are generated till the decrease and higher bounds converge.<\/p>\n

    5. Implementing Benders decomposition with Pyomo and HiGHS<\/h2>\n

    We now have all of the mathematical equipment required to implement the Benders decomposition algorithm mentioned within the earlier sections. The grasp downside will choose the services to open, the twin subproblem will consider the ensuing customer-assignment price, and the generated optimality cuts will progressively enhance the grasp downside.<\/p>\n

    As an example the whole process, we are going to resolve a small uncapacitated facility location occasion containing 5 candidate services and twenty clients<\/strong>. The occasion is saved in JSON format in order that the optimization mannequin stays separate from the info and might simply be reused or modified. Each the occasion and the whole pocket book might be downloaded from the accompanying GitHub repository.<\/a><\/p>\n

    The implementation makes use of Pyomo<\/strong> to formulate the optimization fashions and the open-source HiGHS<\/strong> solver to unravel the grasp and subproblems. We are going to first load and put together the info, then assemble every element of the decomposition algorithm earlier than combining them into the whole iterative process.<\/p>\n

    5.1 Loading and getting ready the occasion<\/h3>\n

    We start by putting in the required packages and importing the libraries used all through the implementation. The JSON occasion is then downloaded straight from the GitHub repository and transformed into the units and dictionaries required by Pyomo.<\/p>\n

    !pip -q set up pyomo highspy\n\nimport requests\nimport pandas as pd\nimport matplotlib.pyplot as plt\nimport pyomo.environ as pyo\n\nfrom pyomo.decide import SolverFactory, TerminationCondition\n# Load the occasion from GitHub\nJSON_URL = (\n    \"https:\/\/uncooked.githubusercontent.com\/ceche1212\/\"\n    \"Benders_Tutorials_TDS\/refs\/heads\/foremost\/Knowledge\/\"\n    \"ufl_benders_5x20_instance.json\"\n)\n\nresponse = requests.get(JSON_URL, timeout=30)\nresponse.raise_for_status()\noccasion = response.json()\n\n# Units\nservices = [facility[\"id\"] for facility in occasion[\"facilities\"]]\nclients = [customer[\"id\"] for buyer in occasion[\"customers\"]]\n\n# Facility parameters\nfixed_cost = {\n    facility[\"id\"]: facility[\"fixed_cost\"]\n    for facility in occasion[\"facilities\"]\n}\n\nfacility_coordinates = {\n    facility[\"id\"]: (facility[\"x\"], facility[\"y\"])\n    for facility in occasion[\"facilities\"]\n}\n\n# Buyer parameters\ndemand = {\n    buyer[\"id\"]: buyer[\"demand\"]\n    for buyer in occasion[\"customers\"]\n}\n\ncustomer_coordinates = {\n    buyer[\"id\"]: (buyer[\"x\"], buyer[\"y\"])\n    for buyer in occasion[\"customers\"]\n}\n\n# Project prices\nassignment_cost = {\n    (file[\"facility\"], file[\"customer\"]): file[\"cost\"]\n    for file in occasion[\"assignment_costs\"]\n}\n\nEarlier than constructing the optimization fashions, we carry out a small validation to verify that every one identifiers are distinctive and that each facility-customer mixture has an task price.\n\nif len(services) != len(set(services)):\n    increase ValueError(\"Duplicate facility IDs have been discovered.\")\n\nif len(clients) != len(set(clients)):\n    increase ValueError(\"Duplicate buyer IDs have been discovered.\")\n\nexpected_pairs = {\n    (facility, buyer)\n    for facility in services\n    for buyer in clients\n}\n\navailable_pairs = set(assignment_cost)\n\nif expected_pairs != available_pairs:\n    missing_pairs = expected_pairs - available_pairs\n    extra_pairs = available_pairs - expected_pairs\n\n    increase ValueError(\n        f\"Lacking task prices: {sorted(missing_pairs)}n\"\n        f\"Surprising task prices: {sorted(extra_pairs)}\"\n    )\n\nprint(\"Occasion loaded efficiently\")\nprint(f\"Identify: {occasion['instance_name']}\")\nprint(f\"Services: {len(services)}\")\nprint(f\"Clients: {len(clients)}\")\nprint(f\"Project prices: {len(assignment_cost)}\")<\/code><\/pre>\n
    The JSON knowledge is reworked into peculiar Python lists and dictionaries. The ability and buyer coordinates will later be used to visualise the ultimate resolution, whereas fixed_cost<\/code> and assignment_cost<\/code> include the parameters required by the grasp and subproblems.<\/p>\n
    5.2 Constructing the preliminary grasp downside<\/h3>\n
    We first assemble the grasp downside, which accommodates solely the strategic facility-opening choices and the variable (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>), representing the present approximation of the customer-assignment price. The ConstraintList<\/code> is initially empty as a result of the Benders optimality cuts can be generated and added throughout the iterative algorithm.<\/p>\n
    # ============================================================\n# Construct the preliminary grasp downside\n# ============================================================\n\ngrasp = pyo.ConcreteModel()\n\ngrasp.FACILITIES = pyo.Set(\n    initialize=services,\n    ordered=True\n)\n\ngrasp.fixed_cost = pyo.Param(\n    grasp.FACILITIES,\n    initialize=fixed_cost\n)\n\n# Facility-opening choices and assignment-cost approximation\ngrasp.x = pyo.Var(\n    grasp.FACILITIES,\n    area=pyo.Binary\n)\n\ngrasp.theta = pyo.Var(\n    area=pyo.NonNegativeReals\n)\n\n# Not less than one facility have to be opened\ngrasp.OpenAtLeastOne = pyo.Constraint(\n    expr=sum(grasp.x[i] for i in grasp.FACILITIES) >= 1\n)\n\n# Optimality cuts can be added throughout the algorithm\ngrasp.BendersCuts = pyo.ConstraintList()\n\ngrasp.TotalCost = pyo.Goal(\n    expr=(\n        sum(\n            grasp.fixed_cost[i] * grasp.x[i]\n            for i in grasp.FACILITIES\n        )\n        + grasp.theta\n    ),\n    sense=pyo.decrease\n)\n\n\n# ============================================================\n# Configure and resolve with HiGHS\n# ============================================================\n\nsolver = SolverFactory(\"appsi_highs\")\n\nsolver.highs_options.replace({\n    \"output_flag\": True,\n    \"mip_rel_gap\": 0.0,\n    \"time_limit\": 360\n})\n\noutcomes = solver.resolve(grasp, tee=True)\n\nif outcomes.solver.termination_condition != TerminationCondition.optimum:\n    increase RuntimeError(\n        \"The preliminary grasp downside was not solved to optimality.\"\n    )\n\n\n# ============================================================\n# Extract the preliminary resolution\n# ============================================================\n\nx_solution = {\n    i: int(spherical(pyo.worth(grasp.x[i])))\n    for i in grasp.FACILITIES\n}\n\ntheta_value = pyo.worth(grasp.theta)\nfixed_cost_value = sum(\n    fixed_cost[i] * x_solution[i]\n    for i in grasp.FACILITIES\n)\nmaster_objective_value = pyo.worth(grasp.TotalCost)\n\nprint(\"nInitial grasp resolution\")\n\nfor i, worth in x_solution.gadgets():\n    standing = \"Open\" if worth else \"Closed\"\n    print(f\"Facility {i}: x = {worth} ({standing})\")\n\nprint(f\"nFixed opening price: {fixed_cost_value:,.2f}\")\nprint(f\"Estimated task price: {theta_value:,.2f}\")\nprint(f\"Grasp goal worth: {master_objective_value:,.2f}\")<\/code><\/pre>\n
    Preliminary grasp resolution\nFacility F1: x = 0 (Closed)\nFacility F2: x = 0 (Closed)\nFacility F3: x = 0 (Closed)\nFacility F4: x = 1 (Open)\nFacility F5: x = 0 (Closed)\n\nFastened opening price: 2,100.00\nEstimated task price: 0.00\nGrasp goal worth: 2,100.00<\/code><\/pre>\n
    The preliminary grasp has no details about the precise task price past its nonnegativity, so it units (\u03b8<\/mi>=<\/mo>0<\/mn><\/mrow>theta=0<\/annotation><\/semantics><\/math>). It subsequently opens solely the power with the bottom fastened price, producing an optimistic decrease sure for the unique downside. The twin subproblem will now consider this facility configuration and generate the primary optimality minimize.<\/p>\n
    5.3 Evaluating the preliminary determination and producing the primary minimize<\/h3>\n
    The preliminary grasp resolution opens the power with the bottom fastened price whereas assuming that buyer assignments price nothing. We now consider this determination utilizing the twin task subproblem derived earlier. The operate under receives the present facility-opening vector (x<\/mi>\u203e<\/mo><\/mover>bar{x}<\/annotation><\/semantics><\/math>), solves the twin downside, and returns the knowledge wanted to assemble an optimality minimize.<\/p>\n
    # ============================================================\n# Construct the twin task subproblem\n# ============================================================\n\ndef build_dual_subproblem(x_bar):\n\n    twin = pyo.ConcreteModel()\n\n    twin.FACILITIES = pyo.Set(\n        initialize=services,\n        ordered=True\n    )\n\n    twin.CUSTOMERS = pyo.Set(\n        initialize=clients,\n        ordered=True\n    )\n\n    twin.assignment_cost = pyo.Param(\n        twin.FACILITIES,\n        twin.CUSTOMERS,\n        initialize=assignment_cost\n    )\n\n    twin.x_bar = pyo.Param(\n        twin.FACILITIES,\n        initialize=x_bar\n    )\n\n    # alpha_j is unrestricted; beta_ij is nonnegative\n    twin.alpha = pyo.Var(\n        twin.CUSTOMERS,\n        area=pyo.Reals\n    )\n\n    twin.beta = pyo.Var(\n        twin.FACILITIES,\n        twin.CUSTOMERS,\n        area=pyo.NonNegativeReals\n    )\n\n    twin.DualFeasibility = pyo.Constraint(\n        twin.FACILITIES,\n        twin.CUSTOMERS,\n        rule=lambda twin, i, j: (\n            twin.alpha[j] - twin.beta[i, j]\n            <= twin.assignment_cost[i, j]\n        )\n    )\n\n    twin.AssignmentCost = pyo.Goal(\n        expr=(\n            sum(\n                twin.alpha[j]\n                for j in twin.CUSTOMERS\n            )\n            -\n            sum(\n                twin.x_bar[i] * twin.beta[i, j]\n                for i in twin.FACILITIES\n                for j in twin.CUSTOMERS\n            )\n        ),\n        sense=pyo.maximize\n    )\n\n    return twin<\/code><\/pre>\n
    # ============================================================\n# Resolve the twin for the preliminary grasp resolution\n# ============================================================\n\ntwin = build_dual_subproblem(x_solution)\ndual_results = solver.resolve(twin, tee=False)\n\nif dual_results.solver.termination_condition != TerminationCondition.optimum:\n    increase RuntimeError(\n        \"The twin subproblem was not solved to optimality.\"\n    )\n\nalpha_solution = {\n    j: pyo.worth(twin.alpha[j])\n    for j in twin.CUSTOMERS\n}\n\nbeta_solution = {\n    (i, j): pyo.worth(twin.beta[i, j])\n    for i in twin.FACILITIES\n    for j in twin.CUSTOMERS\n}\n\nassignment_cost_value = pyo.worth(\n    twin.AssignmentCost\n)\n\nprint(\"nDual subproblem resolution\")\nprint(f\"Project price: {assignment_cost_value:,.2f}\")\n\nprint(\"nAlpha values:\")\nfor j, worth in alpha_solution.gadgets():\n    print(f\"  {j}: {worth:,.2f}\")<\/code><\/pre>\n
    # ============================================================\n# Add the primary Benders optimality minimize\n# ============================================================\n\ncut_expression = (\n    sum(\n        alpha_solution[j]\n        for j in clients\n    )\n    -\n    sum(\n        beta_solution[i, j] * grasp.x[i]\n        for i in services\n        for j in clients\n    )\n)\n\ngrasp.BendersCuts.add(\n    grasp.theta >= cut_expression\n)\n\nprint(\"First Benders optimality minimize added efficiently.\")<\/code><\/pre>\n
    The parameters x_bar<\/code> repair the power choices proposed by the grasp. The variables (\u03b1<\/mi>j<\/mi><\/msub>alpha_j<\/annotation><\/semantics><\/math>) correspond to the customer-assignment equalities, whereas (\u03b2<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>beta_{ij}<\/annotation><\/semantics><\/math>) correspond to the constraints stopping assignments to closed services. Fixing the twin supplies each the true task price of the present configuration and the coefficients required for the minimize. The minimize is then added to grasp.BendersCuts<\/code>. When the grasp is solved once more, it might probably not assign an unrealistically low worth to (\u03b8<\/mi>theta<\/annotation><\/semantics><\/math>) for a similar facility configuration.<\/p>\n
    5.4 Automating the Benders iterations<\/h3>\n
    The earlier cells carried out the primary Benders iteration explicitly. We are able to now automate the identical sequence: resolve the grasp downside, consider its facility configuration with the twin subproblem, replace the decrease and higher bounds, and add a brand new optimality minimize. The process stops when each bounds coincide, proving that the present resolution is perfect.<\/p>\n
    # ============================================================\n# Benders decomposition algorithm\n# ============================================================\n\nmaximum_iterations = 100\ntolerance = 1e-6\n\nlower_bound = -float(\"inf\")\nupper_bound = float(\"inf\")\n\nbest_x_solution = None\nbest_fixed_cost = None\nbest_assignment_cost = None\nbest_total_cost = None\n\niteration_results = []\n\n# Suppress the HiGHS log throughout the iterative process\nsolver.highs_options[\"output_flag\"] = False\nsolver.highs_options[\"log_to_console\"] = False\n\n\nfor iteration in vary(1, maximum_iterations + 1):\n\n    # --------------------------------------------------------\n    # 1. Resolve the grasp downside\n    # --------------------------------------------------------\n    master_results = solver.resolve(grasp, tee=False)\n\n    if master_results.solver.termination_condition != TerminationCondition.optimum:\n        increase RuntimeError(\n            f\"Grasp downside failed at iteration {iteration}.\"\n        )\n\n    x_bar = {\n        i: int(spherical(pyo.worth(grasp.x[i])))\n        for i in grasp.FACILITIES\n    }\n\n    theta_value = pyo.worth(grasp.theta)\n    fixed_cost_value = sum(\n        fixed_cost[i] * x_bar[i]\n        for i in services\n    )\n\n    lower_bound = pyo.worth(grasp.TotalCost)\n\n    # --------------------------------------------------------\n    # 2. Resolve the twin subproblem\n    # --------------------------------------------------------\n    twin = build_dual_subproblem(x_bar)\n    dual_results = solver.resolve(twin, tee=False)\n\n    if dual_results.solver.termination_condition != TerminationCondition.optimum:\n        increase RuntimeError(\n            f\"Twin subproblem failed at iteration {iteration}.\"\n        )\n\n    assignment_cost_value = pyo.worth(twin.AssignmentCost)\n    total_cost = fixed_cost_value + assignment_cost_value\n\n    # --------------------------------------------------------\n    # 3. Replace the perfect possible resolution\n    # --------------------------------------------------------\n    if total_cost < upper_bound:\n        upper_bound = total_cost\n        best_x_solution = dict(x_bar)\n        best_fixed_cost = fixed_cost_value\n        best_assignment_cost = assignment_cost_value\n        best_total_cost = total_cost\n\n    absolute_gap = upper_bound - lower_bound\n    relative_gap = absolute_gap \/ max(1.0, abs(upper_bound))\n\n    open_facilities = [\n        i for i in facilities\n        if x_bar[i] == 1\n    ]\n\n    iteration_results.append({\n        \"iteration\": iteration,\n        \"open services\": \", \".be a part of(open_facilities),\n        \"fastened price\": fixed_cost_value,\n        \"theta\": theta_value,\n        \"task price\": assignment_cost_value,\n        \"decrease sure\": lower_bound,\n        \"higher sure\": upper_bound,\n        \"absolute hole\": absolute_gap,\n        \"relative hole\": relative_gap\n    })\n\n    print(\"-\" * 70)\n    print(f\"Iteration: {iteration}\")\n    print(f\"Open services: {open_facilities}\")\n    print(f\"Fastened price: {fixed_cost_value:,.2f}\")\n    print(f\"Theta: {theta_value:,.2f}\")\n    print(f\"Precise task price: {assignment_cost_value:,.2f}\")\n    print(f\"Decrease sure: {lower_bound:,.2f}\")\n    print(f\"Higher sure: {upper_bound:,.2f}\")\n    print(f\"Relative hole: {100 * relative_gap:.6f}%\")\n\n    # --------------------------------------------------------\n    # 4. Test convergence\n    # --------------------------------------------------------\n    if absolute_gap <= tolerance:\n        print(\"nBenders decomposition converged.\")\n        break\n\n    # --------------------------------------------------------\n    # 5. Generate and add a brand new optimality minimize\n    # --------------------------------------------------------\n    alpha_solution = {\n        j: pyo.worth(twin.alpha[j])\n        for j in twin.CUSTOMERS\n    }\n\n    beta_solution = {\n        (i, j): pyo.worth(twin.beta[i, j])\n        for i in twin.FACILITIES\n        for j in twin.CUSTOMERS\n    }\n\n    cut_expression = (\n        sum(alpha_solution[j] for j in clients)\n        -\n        sum(\n            beta_solution[i, j] * grasp.x[i]\n            for i in services\n            for j in clients\n        )\n    )\n\n    grasp.BendersCuts.add(\n        grasp.theta >= cut_expression\n    )\n\nelse:\n    increase RuntimeError(\n        \"Most variety of iterations reached with out convergence.\"\n    )<\/code><\/pre>\n
    After 9 iterations, the Benders algorithm converges to the optimum resolution. At that time, the decrease sure supplied by the grasp downside and the higher sure obtained from the evaluated subproblem attain the identical worth, which proves optimality.<\/p>\n
    ----------------------------------------------------------------------\nIteration: 1\nOpen services: ['F2', 'F3', 'F5']\nFastened price: 7,000.00\nTheta: 56.00\nPrecise task price: 8,955.00\nDecrease sure: 7,056.00\nHigher sure: 15,955.00\nRelative hole: 55.775619%\n----------------------------------------------------------------------\nIteration: 2\nOpen services: ['F1', 'F2']\nFastened price: 4,600.00\nTheta: 7,306.00\nPrecise task price: 13,781.00\nDecrease sure: 11,906.00\nHigher sure: 15,955.00\nRelative hole: 25.377625%\n----------------------------------------------------------------------\nIteration: 3\nOpen services: ['F2', 'F4', 'F5']\nFastened price: 6,600.00\nTheta: 6,403.00\nPrecise task price: 8,143.00\nDecrease sure: 13,003.00\nHigher sure: 14,743.00\nRelative hole: 11.802211%\n----------------------------------------------------------------------\nIteration: 4\nOpen services: ['F1', 'F3', 'F4', 'F5']\nFastened price: 9,300.00\nTheta: 4,206.00\nPrecise task price: 5,455.00\nDecrease sure: 13,506.00\nHigher sure: 14,743.00\nRelative hole: 8.390423%\n----------------------------------------------------------------------\nIteration: 5\nOpen services: ['F3', 'F5']\nFastened price: 4,800.00\nTheta: 8,955.00\nPrecise task price: 13,792.00\nDecrease sure: 13,755.00\nHigher sure: 14,743.00\nRelative hole: 6.701485%\n----------------------------------------------------------------------\nIteration: 6\nOpen services: ['F2', 'F3', 'F4']\nFastened price: 6,800.00\nTheta: 7,057.00\nPrecise task price: 8,750.00\nDecrease sure: 13,857.00\nHigher sure: 14,743.00\nRelative hole: 6.009632%\n----------------------------------------------------------------------\nIteration: 7\nOpen services: ['F2', 'F5']\nFastened price: 4,500.00\nTheta: 9,594.00\nPrecise task price: 11,243.00\nDecrease sure: 14,094.00\nHigher sure: 14,743.00\nRelative hole: 4.402089%\n----------------------------------------------------------------------\nIteration: 8\nOpen services: ['F1', 'F5']\nFastened price: 4,700.00\nTheta: 9,594.00\nPrecise task price: 12,241.00\nDecrease sure: 14,294.00\nHigher sure: 14,743.00\nRelative hole: 3.045513%\n----------------------------------------------------------------------\nIteration: 9\nOpen services: ['F2', 'F4', 'F5']\nFastened price: 6,600.00\nTheta: 8,143.00\nPrecise task price: 8,143.00\nDecrease sure: 14,743.00\nHigher sure: 14,743.00\nRelative hole: 0.000000%\n\nBenders decomposition converged.\n<\/code><\/pre>\n
    5.5 Recovering the ultimate facility and buyer choices<\/h3>\n
    As soon as the bounds converge, we are able to report the optimum facility configuration and its price. The twin subproblem supplies the task price and the coefficients required to generate cuts, however it doesn’t straight return the primal task variables (y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>y_{ij}<\/annotation><\/semantics><\/math>). We subsequently resolve the primal task subproblem one ultimate time, fixing the services at the perfect resolution discovered by Benders.<\/p>\n
    # ============================================================\n# Show the ultimate Benders resolution\n# ============================================================\n\nprint(\"nFinal Benders resolution\")\nprint(\"=\" * 50)\n\nfor i in services:\n    standing = \"Open\" if best_x_solution[i] else \"Closed\"\n    print(f\"Facility {i}: {standing}\")\n\nprint(f\"nFixed opening price: {best_fixed_cost:,.2f}\")\nprint(f\"Project price: {best_assignment_cost:,.2f}\")\nprint(f\"Complete price: {best_total_cost:,.2f}\")\nprint(f\"Iterations: {iteration}\")<\/code><\/pre>\n
    # ============================================================\n# Construct the ultimate primal task subproblem\n# ============================================================\n\nassignment_model = pyo.ConcreteModel()\n\nassignment_model.FACILITIES = pyo.Set(\n    initialize=services,\n    ordered=True\n)\n\nassignment_model.CUSTOMERS = pyo.Set(\n    initialize=clients,\n    ordered=True\n)\n\nassignment_model.assignment_cost = pyo.Param(\n    assignment_model.FACILITIES,\n    assignment_model.CUSTOMERS,\n    initialize=assignment_cost\n)\n\nassignment_model.x_bar = pyo.Param(\n    assignment_model.FACILITIES,\n    initialize=best_x_solution\n)\n\nassignment_model.y = pyo.Var(\n    assignment_model.FACILITIES,\n    assignment_model.CUSTOMERS,\n    area=pyo.NonNegativeReals\n)\n\nassignment_model.AssignEachCustomer = pyo.Constraint(\n    assignment_model.CUSTOMERS,\n    rule=lambda mannequin, j: sum(\n        mannequin.y[i, j]\n        for i in mannequin.FACILITIES\n    ) == 1\n)\n\nassignment_model.UseOnlyOpenFacilities = pyo.Constraint(\n    assignment_model.FACILITIES,\n    assignment_model.CUSTOMERS,\n    rule=lambda mannequin, i, j: (\n        mannequin.y[i, j] <= mannequin.x_bar[i]\n    )\n)\n\nassignment_model.TotalAssignmentCost = pyo.Goal(\n    expr=sum(\n        assignment_model.assignment_cost[i, j]\n        * assignment_model.y[i, j]\n        for i in assignment_model.FACILITIES\n        for j in assignment_model.CUSTOMERS\n    ),\n    sense=pyo.decrease\n)\n\nassignment_results = solver.resolve(\n    assignment_model,\n    tee=False\n)\n\nif (\n    assignment_results.solver.termination_condition\n    != TerminationCondition.optimum\n):\n    increase RuntimeError(\n        \"The ultimate task downside was not solved to optimality.\"\n    )<\/code><\/pre>\n
    # ============================================================\n# Extract and show the shopper assignments\n# ============================================================\n\nassignment_rows = [\n    {\n        \"customer\": j,\n        \"facility\": i,\n        \"assignment\": pyo.value(assignment_model.y[i, j]),\n        \"demand\": demand[j],\n        \"task price\": assignment_cost[i, j]\n    }\n    for j in clients\n    for i in services\n    if pyo.worth(assignment_model.y[i, j]) > 1e-6\n]\n\nassignment_table = pd.DataFrame(assignment_rows)\n\nshow(\n    assignment_table.fashion.format({\n        \"task\": \"{:.2f}\",\n        \"demand\": \"{:,.0f}\",\n        \"task price\": \"{:,.2f}\"\n    })\n)<\/code><\/pre>\n
    The ultimate output identifies the services chosen by the grasp downside and separates the entire goal into fastened opening and customer-assignment prices. We then repair these facility choices within the primal subproblem and get better the corresponding (y<\/mi>i<\/mi>j<\/mi><\/mrow><\/msub>y_{ij}<\/annotation><\/semantics><\/math>) values. The ensuing desk exhibits which open facility serves every buyer, along with the related demand and task price.<\/p>\n
    \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    \u00a0<\/th>\nbuyer<\/th>\nfacility<\/th>\ntask<\/th>\ndemand<\/th>\ntask price<\/th>\n<\/tr>\n<\/thead>\n
    0<\/th>\nC1<\/td>\nF2<\/td>\n1.00<\/td>\n2<\/td>\n537.00<\/td>\n<\/tr>\n
    1<\/th>\nC2<\/td>\nF2<\/td>\n1.00<\/td>\n3<\/td>\n562.00<\/td>\n<\/tr>\n
    2<\/th>\nC3<\/td>\nF2<\/td>\n1.00<\/td>\n1<\/td>\n215.00<\/td>\n<\/tr>\n
    3<\/th>\nC4<\/td>\nF2<\/td>\n1.00<\/td>\n4<\/td>\n1,024.00<\/td>\n<\/tr>\n
    4<\/th>\nC5<\/td>\nF2<\/td>\n1.00<\/td>\n2<\/td>\n113.00<\/td>\n<\/tr>\n
    5<\/th>\nC6<\/td>\nF2<\/td>\n1.00<\/td>\n3<\/td>\n129.00<\/td>\n<\/tr>\n
    6<\/th>\nC7<\/td>\nF2<\/td>\n1.00<\/td>\n2<\/td>\n195.00<\/td>\n<\/tr>\n
    7<\/th>\nC8<\/td>\nF2<\/td>\n1.00<\/td>\n1<\/td>\n115.00<\/td>\n<\/tr>\n
    8<\/th>\nC9<\/td>\nF2<\/td>\n1.00<\/td>\n3<\/td>\n840.00<\/td>\n<\/tr>\n
    9<\/th>\nC10<\/td>\nF2<\/td>\n1.00<\/td>\n2<\/td>\n691.00<\/td>\n<\/tr>\n
    10<\/th>\nC11<\/td>\nF2<\/td>\n1.00<\/td>\n4<\/td>\n1,152.00<\/td>\n<\/tr>\n
    11<\/th>\nC12<\/td>\nF2<\/td>\n1.00<\/td>\n1<\/td>\n437.00<\/td>\n<\/tr>\n
    12<\/th>\nC13<\/td>\nF4<\/td>\n1.00<\/td>\n3<\/td>\n206.00<\/td>\n<\/tr>\n
    13<\/th>\nC14<\/td>\nF4<\/td>\n1.00<\/td>\n2<\/td>\n113.00<\/td>\n<\/tr>\n
    14<\/th>\nC15<\/td>\nF4<\/td>\n1.00<\/td>\n4<\/td>\n525.00<\/td>\n<\/tr>\n
    15<\/th>\nC16<\/td>\nF4<\/td>\n1.00<\/td>\n1<\/td>\n131.00<\/td>\n<\/tr>\n
    16<\/th>\nC17<\/td>\nF5<\/td>\n1.00<\/td>\n2<\/td>\n138.00<\/td>\n<\/tr>\n
    17<\/th>\nC18<\/td>\nF5<\/td>\n1.00<\/td>\n3<\/td>\n170.00<\/td>\n<\/tr>\n
    18<\/th>\nC19<\/td>\nF5<\/td>\n1.00<\/td>\n2<\/td>\n262.00<\/td>\n<\/tr>\n
    19<\/th>\nC20<\/td>\nF5<\/td>\n1.00<\/td>\n4<\/td>\n588.00<\/td>\n<\/tr>\n<\/tbody>\n<\/table>
    Desk 1. Optimum Resolution, open services and assingments.<\/figcaption><\/figure>\n
    The task desk is helpful for verification, however a determine supplies a a lot clearer overview of the answer. Within the subsequent cell, we create a easy plot exhibiting which services are open, that are closed, and the way clients are assigned to the chosen services.<\/p>\n
    # ============================================================\n# Visualize the ultimate facility-location resolution\n# ============================================================\n\nfig, ax = plt.subplots(figsize=(12, 8))\n\nopen_facilities = [i for i in facilities if best_x_solution[i] == 1]\nclosed_facilities = [i for i in facilities if best_x_solution[i] == 0]\n\n# Plot task connections\nfor _, row in assignment_table.iterrows():\n    facility, buyer = row[\"facility\"], row[\"customer\"]\n    fx, fy = facility_coordinates[facility]\n    cx, cy = customer_coordinates[customer]\n\n    ax.plot(\n        [fx, cx], [fy, cy],\n        linewidth=1.2,\n        alpha=0.55 * row[\"assignment\"],\n        zorder=1\n    )\n\n# Plot clients\nax.scatter(\n    [customer_coordinates[j][0] for j in clients],\n    [customer_coordinates[j][1] for j in clients],\n    marker=\"o\",\n    s=70,\n    label=\"Clients\",\n    zorder=3\n)\n\n# Plot open services\nax.scatter(\n    [facility_coordinates[i][0] for i in open_facilities],\n    [facility_coordinates[i][1] for i in open_facilities],\n    marker=\"*\",\n    s=350,\n    label=\"Open services\",\n    zorder=4\n)\n\n# Plot closed services\nax.scatter(\n    [facility_coordinates[i][0] for i in closed_facilities],\n    [facility_coordinates[i][1] for i in closed_facilities],\n    marker=\"X\",\n    s=150,\n    alpha=0.45,\n    label=\"Closed services\",\n    zorder=2\n)\n\n# Add buyer labels\nfor buyer in clients:\n    x, y = customer_coordinates[customer]\n    ax.annotate(\n        buyer, (x, y),\n        xytext=(5, 5),\n        textcoords=\"offset factors\",\n        fontsize=9\n    )\n\n# Add facility labels\nfor facility in services:\n    x, y = facility_coordinates[facility]\n    standing = \"Open\" if best_x_solution[facility] else \"Closed\"\n\n    ax.annotate(\n        f\"{facility}n{standing}\",\n        (x, y),\n        xytext=(7, 7),\n        textcoords=\"offset factors\",\n        fontsize=10,\n        fontweight=\"daring\"\n    )\n\nax.set_title(\"Optimum Uncapacitated Facility Location Resolution\", fontsize=15)\nax.set_xlabel(\"X coordinate\")\nax.set_ylabel(\"Y coordinate\")\nax.set_aspect(\"equal\", adjustable=\"field\")\nax.grid(alpha=0.25)\nax.legend()\n\nplt.tight_layout()\nplt.present()<\/code><\/pre>\n
    The plot supplies a hen\u2019s-eye view of the optimum resolution. Open services are proven with star markers, closed services with X<\/code> markers, and clients with circles. The connecting segments point out which facility serves every buyer, making it straightforward to interpret the geographic construction of the answer at a look.<\/p>\n
    \"\"
    Determine 2. Eye view of the optimum resolution with the open services and clients assigned to every (Picture generated by the creator)<\/figcaption><\/figure>\n
    Conclusions<\/h2>\n
    On this article, we explored the central mechanism of classical Benders decomposition. The grasp downside chosen which services to open, the subproblem evaluated the ensuing task price, and the twin resolution generated optimality cuts that regularly corrected the grasp\u2019s initially optimistic estimate. We then applied the whole algorithm in Python utilizing Pyomo and the open-source HiGHS solver.<\/p>\n
    Benders decomposition is an awfully highly effective approach, however it’s not assured to outperform the equal monolithic formulation. For a small occasion, a contemporary solver might resolve the whole mannequin virtually instantly. In that state of affairs, developing separate grasp and subproblems, transferring options between them, producing cuts, and repeatedly fixing the fashions might introduce extra computational overhead than profit. Decomposition ought to subsequently not be adopted just because it seems extra subtle.<\/p>\n
    It’s not a silver bullet both. Benders decomposition requires an issue with an exploitable construction, the place fixing a set of complicating variables leaves a subproblem that’s considerably simpler to unravel. Even when this construction exists, efficiency relies upon closely on the standard of the generated cuts. Weak cuts might present little or no data, forcing the algorithm to finish many iterations earlier than the grasp obtains a sufficiently correct illustration of the subproblem. In follow, a lot of the artwork of designing an efficient Benders algorithm lies in producing stronger cuts, eradicating redundant ones, producing a number of cuts, or exploiting further problem-specific information.<\/p>\n
    The implementation introduced on this article is usually referred to as an outer-loop Benders algorithm<\/strong>. Python explicitly solves the grasp, solves the subproblem, provides a minimize, after which solves the grasp once more. This method is extraordinarily helpful for studying as a result of each step of the algorithm stays seen. Nevertheless, the grasp is repeatedly handed again to the solver as a substitute of permitting the whole process to function straight inside a single branch-and-cut search.<\/p>\n
    Industrial solvers corresponding to Gurobi and CPLEX assist callback mechanisms by which cuts might be generated whereas the solver is exploring the branch-and-cut tree. Moderately than repeatedly terminating and restarting the grasp optimization course of, a callback can examine candidate or leisure options and add lazy constraints or person cuts throughout the search. Relying on the issue and the energy of the cuts, this could produce a considerable enchancment in computational efficiency. <\/p>\n
    Nonetheless, the worth of Benders decomposition shouldn’t be restricted to fixing an issue sooner. Generally decomposition makes it attainable to unravel an issue that can’t even be represented as a monolithic mannequin on the accessible {hardware}.<\/p>\n
    I’m presently encountering exactly this case in certainly one of my analysis initiatives involving a variation of the power location downside. On our analysis machine, which has 128 GB of RAM, making an attempt to assemble the whole monolithic mannequin exhausts the accessible reminiscence earlier than the solver may even start optimizing it. The machine merely reviews that there’s inadequate reminiscence to construct the formulation. With Benders decomposition, nevertheless, we don’t have to create and preserve all grasp and operational variables concurrently. By separating the issue and producing solely the knowledge required by the grasp, we are able to deal with cases that might in any other case stay utterly inaccessible.<\/p>\n
    That is one other aspect of the ability of decomposition. Generally Benders helps us resolve a mannequin extra effectively. Generally it permits us to unravel a mannequin that can’t slot in reminiscence within the first place.<\/p>\n
    To maintain this primary introduction as pleasant as attainable, we intentionally thought of a setting wherein the subproblem was at all times possible. By requiring no less than one facility to open and assuming that each facility might serve each buyer, every grasp determination might at all times be translated into a sound task. The one query was how costly that task can be.<\/p>\n
    However Benders decomposition shouldn’t be at all times this properly behaved. What occurs when the grasp proposes a strategic determination for which no possible operational plan exists? In that state of affairs, the subproblem can not return an optimum price as a result of there isn’t any possible resolution to judge. As an alternative, the algorithm requires a unique sort of suggestions: a feasibility minimize<\/strong> that blocks the present determination and, ideally, a whole household of equally inconceivable choices.<\/p>\n
    That would be the topic of How Benders Decomposition Works, Half II: Feasibility Cuts<\/strong>. We are going to examine the capacitated facility location downside, the place every facility can serve solely a restricted quantity of demand. The grasp might subsequently open inadequate capability and render the task subproblem infeasible. We are going to look at how feasibility cuts permit Benders decomposition to be taught from these failures and proceed looking for an optimum resolution.<\/p>\n
    I sincerely hope you discovered this text helpful and that it made Benders decomposition really feel rather less mysterious. Be at liberty to go away a remark or present your appreciation with a clap \ud83d\udc4f.<\/p>\n
    You may also comply with the most recent work from S\u00e1vila Training<\/a> and join with me on LinkedIn<\/a>. All of the code and knowledge used on this article might be discovered within the accompanying GitHub repository.<\/a><\/p>\n
    Thanks for taking the time to learn. See you in Half II.<\/p>\n
    References<\/h2>\n
    [1] McCloskey, J. F. (1987). U.S. operations analysis in World Struggle II. Operations Analysis, 35<\/em>(6), 910-925. DOI: 10.1287\/opre.35.6.910.<\/p>\n
    [2] Dantzig, G. B. (1982). Reminiscences in regards to the origins of linear programming. Operations Analysis Letters, 1<\/em>(2), 43-48. DOI: 10.1016\/0167-6377(82)90043-8.<\/p>\n
    [3] Dantzig, G. B. (1951). Maximization of a linear operate of variables topic to linear inequalities. In T. C. Koopmans (Ed.), Exercise evaluation of manufacturing and allocation<\/em> (pp. 339-347). John Wiley & Sons.<\/p>\n
    [4] Aardal, Ok. I., Hurkens, C. A. J., & Lenstra, J. Ok. (2025). Jacques Benders and his decomposition algorithm. Operations Analysis Letters, 63<\/em>, Article 107361. DOI: 10.1016\/j.orl.2025.107361.<\/p>\n
    [5] Benders, J. F. (1960). Partitioning in mathematical programming<\/em> [Doctoral dissertation, Utrecht University].<\/p>\n
    [6] Benders, J. F. (1962). Partitioning procedures for fixing mixed-variables programming issues. Numerische Mathematik, 4<\/em>, 238-252. DOI: 10.1007\/BF01386316.<\/p>\n
    [7] Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature overview. European Journal of Operational Analysis, 259<\/em>(3), 801-817. DOI: 10.1016\/j.ejor.2016.12.005.<\/p>\n<\/div>\n\n","protected":false},"excerpt":{"rendered":"
    army planners with coordination issues on a scale that had not often been imagined. Plane, personnel, gas, gear, coaching, and provides needed to be allotted throughout an immense system, usually below extreme time strain and uncertainty. This setting accelerated the event of operations analysis, a self-discipline based on the concept that advanced choices could possibly […]<\/p>\n","protected":false},"author":2,"featured_media":17269,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[55],"tags":[9987,2885,9988,9989,668,431],"class_list":["post-17267","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-machine-learning","tag-benders","tag-cuts","tag-decomposition","tag-optimality","tag-part","tag-works"],"_links":{"self":[{"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/posts\/17267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17267"}],"version-history":[{"count":1,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/posts\/17267\/revisions"}],"predecessor-version":[{"id":17268,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/posts\/17267\/revisions\/17268"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=\/wp\/v2\/media\/17269"}],"wp:attachment":[{"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techtrendfeed.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}