How Benders Decomposition Works, Half II: Feasibility Cuts

of this collection, we explored Benders decomposition in its friendliest attainable setting. The grasp drawback made strategic choices, the subproblem evaluated their operational penalties, and each grasp answer produced a possible operational plan. The grasp might underestimate the true operational price or suggest a really poor determination, however the subproblem might at all times reply with a sound goal worth.

That worth allowed us to generate an optimality minimize. The subproblem successfully advised the grasp that its determination was possible, however that working beneath it could price greater than anticipated. The grasp integrated this suggestions, improved its approximation of the operational price, and tried once more. Via this iterative change, the decrease and higher bounds step by step converged to the optimum answer.

Many optimization issues, nevertheless, will not be almost so cooperative. Suppose, we’re coping with a facility location drawback with restricted manufacturing capacities on every facility, and that the grasp decides which services to open, whereas the subproblem should assign buyer demand to them. The grasp might choose the most cost effective facility and procure an apparently enticing mounted price, just for the subproblem to find that the chosen facility doesn’t have sufficient capability to serve all clients. The identical state of affairs can come up when sure clients can solely be served by particular services, when too few staff are employed, when inadequate machines are activated, or when the chosen autos can’t fulfill all transportation necessities.

In these instances, if we solely have optimality cuts, then the subproblem can’t inform the grasp how costly its determination can be as a result of no possible operational answer exists. The issue is not that the operational price has been underestimated. The strategic determination itself can’t be carried out.

This creates an vital issue for Benders decomposition. An infeasible subproblem can’t present the standard optimality minimize, and the corresponding grasp answer can’t be used to replace the higher sure. Merely reporting that the subproblem is infeasible can be inadequate. The grasp wants mathematical data that explains which strategic choices should be averted and the way it ought to modify its subsequent proposal.

Benders feasibility cuts present this data. Not like optimality cuts, which enhance the approximation of the operational price, feasibility cuts limit the grasp to choices that admit no less than one possible operational answer. A powerful feasibility minimize does greater than reject the present grasp answer. It captures the structural motive for its failure and may exclude many different choices that will produce the identical operational impossibility.

The mathematical software that permits us to assemble these cuts is Farkas’ lemma. This basic outcome from linear programming supplies a certificates proving {that a} system of linear constraints has no possible answer. The certificates can then be remodeled right into a constraint involving the grasp variables, changing the failure of the subproblem into helpful suggestions for the following grasp iteration.

On this second article, we are going to start with a small optimization drawback during which the preliminary grasp determination makes the subproblem infeasible. We’ll resolve the issue manually, introduce Farkas’ lemma as a theorem of alternate options, assemble an specific certificates of infeasibility, and rework that certificates right into a Benders feasibility minimize. We’ll then proceed the algorithm and observe how feasibility and optimality cuts work collectively till the decrease and higher bounds converge.

As soon as the mechanism is absolutely seen, we are going to apply the identical reasoning to the capacitated facility location drawback. Not like the uncapacitated mannequin studied in Half I, opening no less than one facility not ensures that each buyer might be served. Lastly, we are going to implement the whole algorithm that solves the capacitated facility location drawback in Python utilizing Pyomo and the open-source HiGHS solver. The ensuing Benders loop will generate feasibility cuts at any time when the operational subproblem is unattainable, and optimality cuts at any time when a possible operational plan exists.

Half I confirmed how Benders decomposition learns {that a} determination is dearer than anticipated. Half II reveals the way it learns {that a} determination can’t work in any respect.

2. A small Toy drawback with an infeasible subproblem

Earlier than shifting to capacitated facility location drawback, allow us to first look at a small optimization toy drawback during which the grasp proposes a call that can’t help any possible operational answer. The instance is deliberately easy in order that we are able to observe each step manually and focus fully on the brand new issue launched by infeasibility.

We’ll first formulate the issue and resolve its preliminary grasp drawback. We’ll then present why the corresponding subproblem is infeasible, use Farkas’ lemma to assemble a certificates of infeasibility, and rework that certificates right into a Benders feasibility minimize. Lastly, we are going to proceed the algorithm and observe how feasibility and optimality cuts work collectively till the bounds converge.

2.1 The toy optimization drawback

Take into account a small planning drawback during which two assets might be activated to fulfill a requirement of six items. The primary useful resource can present as much as six items however is comparatively costly to activate and function. The second useful resource is cheaper, however it might probably present at most 4 items and subsequently can’t fulfill the demand by itself

Let ($x_1$) and ($x_2$) point out whether or not the 2 assets are activated. The continual variables ($y_1$) and ($y_2$) symbolize the portions provided by every useful resource. The entire optimization drawback is:

$min quad 5x_1+x_2+2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 6x_1,$

$y_2leq 4x_2,$

$x_1+x_2geq 1,$

$x_1,x_2in{0,1},$

$y_1,y_2geq 0.$

Activating the primary useful resource prices 5 items, whereas activating the second prices just one. As soon as activated, every unit provided by the primary useful resource prices two items, whereas every unit provided by the second prices one.

The primary constraint requires the 2 assets to collectively fulfill the demand of six items. The following two constraints restrict the amount provided by every useful resource in line with its activation determination and accessible capability. Lastly, no less than one useful resource should be activated.

The second useful resource initially seems notably enticing as a result of it has each the bottom activation price and the bottom working price. Nevertheless, its capability is just 4 items. As we are going to see, this encourages the preliminary grasp drawback to pick out a call that appears cheap however can’t fulfill the operational necessities.

2.2 The preliminary grasp drawback

Benders decomposition begins by inserting the strategic activation variables ($x_1$) and ($x_2$) within the grasp drawback. The operational variables ($y_1$) and ($y_2$) are briefly eliminated and changed by the variable ($theta$), which represents an estimate of the operational price. The preliminary grasp drawback is:

$min quad 5x_1+x_2+theta$

topic to

$x_1+x_2geq 1,$

$thetageq 0,$

$x_1,x_2in{0,1}.$

At this stage, the grasp has not but obtained any feasibility or optimality cuts. It solely is aware of that no less than one useful resource should be activated and that the operational price can’t be adverse. As a result of the second useful resource has the bottom activation price, the preliminary grasp answer is:

$bar{x}_1=0, qquad bar{x}_2=1, qquad theta=0.$

The corresponding goal worth is, $LB=1.$

This worth supplies a decrease sure on the optimum goal as a result of the grasp is presently ignoring the true operational penalties of its determination. The grasp believes that activating solely the second useful resource is ample and that the operational price might be zero.

The following step is to ship the choice ($bar{x}=(0,1)$) to the subproblem and decide whether or not a possible operational plan exists.

2.3 The primary subproblem is infeasible

The grasp has proposed the strategic determination:

$bar{x}_1=0, qquad bar{x}_2=1.$

To judge this determination, we repair the activation variables at these values and optimize solely the operational variables ($y_1$) and ($y_2$). The subproblem goal is:

$Q(bar{x})=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 6bar{x}_1,$

$y_2leq 4bar{x}_2,$

$y_1,y_2geq 0.$

Substituting the present grasp answer into the capability constraints offers:

$y_1leq 6(0)=0,$

$y_2leq 4(1)=4.$

The entire subproblem is subsequently:

$Q(0,1)=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 0,$

$y_2leq 4,$

$y_1,y_2geq 0.$

The nonnegativity constraint and the higher sure on ($y_1$) pressure:

$y_1=0.$

The most important attainable worth of ($y_2$) is:

$y_2=4.$

Consequently, the utmost amount that may be provided is:

$y_1+y_2leq 4.$

Nevertheless, the demand constraint requires:

$y_1+y_2geq 6.$

These two circumstances can’t be happy concurrently. The subproblem is subsequently infeasible.

This result’s essentially totally different from the conditions studied in Half I. The subproblem doesn’t return a big operational price. It returns no operational price in any respect as a result of the grasp determination can’t help any possible operational plan.

The present answer can’t be used to replace the higher sure, and the standard optimality minimize can’t be generated. As a substitute, we want a mathematical certificates that explains why the subproblem is infeasible and transforms that clarification into a brand new constraint for the grasp drawback.

2.4 Understanding Farkas’ lemma

The subproblem generated by the grasp determination ($bar{x}=(0,1)$) is infeasible. A solver can report this standing, however the phrase “infeasible” alone doesn’t assist the grasp select a greater answer. Benders decomposition requires mathematical data that identifies the supply of the infeasibility and converts it into a brand new constraint.

Farkas’ lemma supplies this data. It’s a theorem of alternate options for techniques of linear inequalities. In easy phrases, it states that both a system of linear constraints has a possible answer, or one other vector exists that proves that no possible answer is feasible. Each alternate options can’t maintain concurrently.

2.4.1 A system of linear inequalities

Take into account the next system:

$Bygeq h,$

$ygeq 0.$

The vector ($y$) comprises the variables whose feasibility we need to decide. The matrix ($B$) comprises their coefficients, whereas ($h$) comprises the right-hand sides of the constraints.

There are two attainable outcomes. The primary is that we are able to discover a nonnegative vector ($y$) satisfying each constraint. On this case, the system is possible.

The second risk is that no such vector exists. Farkas’ lemma states that, when the system is infeasible, we are able to discover one other vector ($r$) satisfying:

$rgeq 0,$

$B^prime rleq 0,$

$h^prime r>0.$

The vector ($r$) is named a certificates of infeasibility, a Farkas certificates, or, in some computational contexts, a twin ray.

Farkas’ lemma subsequently states that precisely one of many following alternate options holds.

The primary various is (the system is possible):

$exists, ygeq 0 quad textual content{such that} quad Bygeq h.$

The second various is (the will not be possible):

$exists, rgeq 0 quad textual content{such that} quad B^prime rleq 0$

and

$h^prime r>0.$

If a possible vector ($y$) exists, no Farkas certificates can exist. Conversely, if a Farkas certificates exists, no possible vector ($y$) can exist.

2.4.2 Why does the certificates show infeasibility?

The circumstances imposed on ($r$) might initially seem summary. Their which means turns into clearer if we assume, briefly, that each a possible answer ($y$) and a certificates ($r$) exist.

As a result of we assume ($y$) is possible, now we have:

$Bygeq h.$

As a result of each part of ($r$) is nonnegative, we are able to multiply every constraint by its corresponding part of ($r$) and add the ensuing inequalities. This provides:

$r^prime Bygeq r^prime h.$

The left-hand facet will also be written as:

$r^prime By=y^prime B^prime r.$

The certificates requires:

$B^prime rleq 0.$

As a result of ($ygeq0$), multiplying the nonpositive vector ($B^prime r$) by the nonnegative vector ($y$) offers:

$y^prime B^prime rleq 0.$

Due to this fact:

$r^prime Byleq 0.$

Nevertheless, the ultimate situation of the Farkas certificates requires:

$r^prime h>0.$

Combining these outcomes offers:

$0geq r^prime Bygeq r^prime h>0.$

That is unattainable. A amount can’t be each nonpositive and strictly constructive.

The contradiction proves {that a} possible vector ($y$) and a Farkas certificates ($r$) can’t exist concurrently. Due to this fact, discovering a vector ($r$) satisfying the certificates circumstances proves that the unique system is infeasible.

2.4.3 Making use of Farkas’ lemma to a Benders subproblem

Take into account a generic Benders subproblem for a set grasp answer ($bar{x}$):

$Q(bar{x})=min_y quad d^prime y$

topic to

$Bygeq b-Abar{x},$

$ygeq 0.$

For the second, the target operate will not be vital. Earlier than minimizing the operational price, we should decide whether or not there may be any vector ($y$) satisfying the constraints.

The feasibility system is:

$Bygeq b-Abar{x},$

$ygeq 0.$

Within the notation of Farkas’ lemma, the right-hand facet is:

$h(bar{x})=b-Abar{x}.$

If the subproblem is infeasible, Farkas’ lemma ensures the existence of a vector ($r$) satisfying:

$rgeq 0,$

$B^prime rleq 0,$

$left(b-Abar{x}proper)^prime r>0.$

The primary two circumstances rely solely on the construction of the subproblem. They be sure that ($r$) is a sound mixture of its constraints.

The third situation depends upon the present grasp answer ($bar{x}$). It reveals that this specific strategic determination produces a contradiction within the operational constraints.

2.4.4 From a certificates to a feasibility minimize

Suppose that the vector ($r^ok$) supplies a certificates for the present grasp answer ($bar{x}$). We subsequently have:

$left(b-Abar{x}proper)^prime r^ok>0.$

This inequality proves that ($bar{x}$) produces an infeasible subproblem.

Nevertheless, the target of Benders decomposition will not be merely to establish that the present determination has failed. We have to assemble a constraint that forestalls the grasp from selecting choices that produce the identical contradiction.

For any grasp determination ($x$) that admits a possible subproblem, the Farkas contradiction should not happen. Consequently, each possible grasp determination should fulfill:

$left(b-Axright)^prime r^kleq 0.$

It is a Benders feasibility minimize. The minimize will also be expanded as:

$b^prime r^k-x^prime A^prime r^kleq 0.$

Equivalently:

$x^prime A^prime r^kgeq b^prime r^ok.$

The present answer ($bar{x}$) violates this inequality as a result of:

$left(b-Abar{x}proper)^prime r^ok>0.$

The minimize subsequently removes the present infeasible grasp answer. Extra importantly, it might probably additionally take away different grasp choices that will create the identical operational contradiction.

That is why the Farkas certificates is extra helpful than a easy infeasibility standing. It explains how the grasp variables are related to the failure of the subproblem and interprets that clarification into a sound grasp constraint.

2.4.5 How can the certificates be obtained?

For a really small drawback, we might be able to establish a certificates manually by inspecting and mixing the constraints. That is what we are going to do with our toy instance.

For bigger issues, the certificates might be obtained computationally. One risk is to request an infeasibility ray straight from the linear programming solver. Some solver interfaces present this data when an LP is infeasible.

One other risk is to unravel an auxiliary optimization drawback that searches for a Farkas certificates. For the present grasp answer ($bar{x}$), contemplate:

$max_r quad left(b-Abar{x}proper)^prime r$

topic to

$B^prime rleq 0,$

$sum_i r_ileq 1,$

$rgeq 0.$

The normalization constraint $sum_i r_ileq 1$, is critical as a result of the certificates circumstances outline a cone. If ($r$) is a certificates, then any constructive a number of of ($r$) can be a certificates. With out normalization, the auxiliary drawback might change into unbounded.

If the optimum goal worth of this auxiliary drawback is strictly constructive, the ensuing vector ($r$) satisfies:

$left(b-Abar{x}proper)^prime r>0,$

and subsequently certifies that the subproblem is infeasible. The corresponding feasibility minimize is then:

$left(b-Axright)^prime rleq 0.$

If the auxiliary goal can’t change into constructive, no Farkas certificates exists for the present right-hand facet. Underneath the circumstances of Farkas’ lemma, because of this the unique feasibility system admits an answer ($y$).

The entire process can subsequently be summarized as follows. First, repair the present grasp answer ($bar{x}$). Second, decide whether or not the operational constraints admit a possible ($y$). If they don’t, discover a Farkas certificates ($r$). Lastly, change ($bar{x}$) with the grasp variables ($x$) within the certificates situation and reverse the strict violation into a sound feasibility requirement:

$left(b-Abar{x}proper)^prime r>0$

turns into

$left(b-Axright)^prime rleq 0.$

We are able to now apply every of those steps to the infeasible subproblem of our toy instance.

2.5 Making use of Farkas’ lemma to the toy subproblem

The grasp answer ($bar{x}=(0,1)$) produced the next infeasible subproblem:

$Q(0,1)=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 0,$

$y_2leq 4,$

$y_1,y_2geq 0.$

To use Farkas’ lemma, we briefly ignore the target operate. The query will not be but how a lot the operational answer prices, however whether or not any operational answer exists.

2.5.1 Rewriting the subproblem in a typical inequality course

Farkas’ lemma was introduced for a system of the shape:

$Bygeq h.$

The demand constraint already makes use of the required greater-than-or-equal-to course:

$y_1+y_2geq 6.$

The capability constraints should subsequently be multiplied by (-1). Earlier than substituting the present grasp determination, they are often written as:

$-y_1geq -6x_1,$

$-y_2geq -4x_2.$

The feasibility system for a generic grasp determination (x) is consequently:

$y_1+y_2geq 6,$

$-y_1geq -6x_1,$

$-y_2geq -4x_2,$

$y_1,y_2geq 0.$

Utilizing matrix notation, the vector of operational variables and The coefficient matrix is:

$y= start{bmatrix} y_1 y_2 finish{bmatrix} qquad B= start{bmatrix} 1 & 1 -1 & 0 0 & -1 finish{bmatrix}.$

The fitting-hand facet depends upon the grasp variables:

$h(x)= start{bmatrix} 6 -6x_1 -4x_2 finish{bmatrix}.$

The operational feasibility system can subsequently be written as:

$Bygeq h(x),$

$ygeq 0.$

For the present grasp answer ($bar{x}=(0,1)$), the right-hand facet turns into:

$h(bar{x})= start{bmatrix} 6 0 -4 finish{bmatrix}.$

2.5.2 Developing the certificates

We affiliate one Farkas multiplier with every constraint. Let:

$r= start{bmatrix} r_1 r_2 r_3 finish{bmatrix}.$

The multiplier ($r_1$) is related to the demand constraint, ($r_2$) with the capability of the primary useful resource, and ($r_3$) with the capability of the second useful resource.

A legitimate Farkas certificates should first fulfill $r_1,r_2,r_3geq 0.$ It should additionally fulfill, $B^prime rleq 0.$ Utilizing the matrix ($B$), we get hold of:

$B^prime r= start{bmatrix} 1 & -1 & 0 1 & 0 & -1 finish{bmatrix} start{bmatrix} r_1 r_2 r_3 finish{bmatrix}.$

Due to this fact:

$B^prime r= start{bmatrix} r_1-r_2 r_1-r_3 finish{bmatrix}.$

The situation ($B^prime rleq0$) turns into:

$r_1-r_2leq 0, qquad r_1-r_3leq 0.$

Equivalently:

$r_2geq r_1, qquad r_3geq r_1.$

We now want the certificates to show that the present right-hand facet is inconsistent. This requires:

$h(bar{x})^prime r>0.$

Substituting the present grasp answer offers:

$h(bar{x})^prime r = 6r_1-4r_3.$

We should subsequently discover nonnegative multipliers satisfying:

$r_2geq r_1, qquad r_3geq r_1, qquad 6r_1-4r_3>0.$

The only alternative is:

$r_1=1, quad r_2=1, quad r_3=1.$

Thus:

$r= start{bmatrix} 1 1 1 finish{bmatrix}.$

2.5.3 Reworking the certificates right into a feasibility minimize

We first confirm the nonnegativity situation.

The Farkas certificates ($r$), was obtained for the present grasp answer ($bar{x}=(0,1)$). To create a Benders minimize, we return to the generic right-hand facet:

$h(x)= start{bmatrix} 6 -6x_1 -4x_2 finish{bmatrix}.$

Utilizing the certificates ($r=(1,1,1)$), we get hold of:

$h(x)^prime r = 6-6x_1-4x_2.$

Any grasp determination that produces a possible subproblem should forestall this expression from being strictly constructive. It should subsequently fulfill:

$6-6x_1-4x_2leq 0.$

Rearranging the inequality offers:

$6x_1+4x_2geq 6.$

That is the Benders feasibility minimize generated by the infeasible subproblem. The present grasp ($bar{x}=(0,1)$) answer violates the minimize as a result of:

$6(0)+4(1)=4<6.$

The minimize subsequently removes ($bar{x}=(0,1)$) from the grasp drawback. Its which means can be intuitive: the activated assets should present no less than six items of whole capability. The vital level is that this constraint was not added manually based mostly on our interpretation of the issue. It was derived systematically from the Farkas certificates returned by the infeasible subproblem. The grasp has now realized why its first determination failed and what situation future choices should fulfill.

2.6 Finishing the toy instance

The primary grasp answer was infeasible, however its Farkas certificates generated the next feasibility minimize, $6x_1+4x_2geq 6.$ The up to date grasp drawback is then:

$min quad 5x_1+x_2+theta$

topic to

$x_1+x_2geq 1,$

$6x_1+4x_2geq 6,$

$thetageq 0,$

$x_1,x_2in{0,1}.$

The earlier answer ($bar{x}=(0,1)$) is not possible as a result of it supplies solely 4 items of capability. The least costly remaining grasp answer is:

$bar{x}_1=1, qquad bar{x}_2=0, qquad theta=0.$

The corresponding grasp goal worth is, $LB=5.$

This worth turns into the brand new decrease sure. The feasibility minimize ensures that the choice has sufficient whole capability, however the grasp nonetheless assumes that the operational price ($theta$) might be zero. We should subsequently ship ($bar{x}=(1,0)$) to the subproblem.

2.6.1 Evaluating the brand new grasp determination

For the choice ($bar{x}=(1,0)$), the operational subproblem is:

$Q(1,0)=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 6,$

$y_2leq 0,$

$y_1,y_2geq 0.$

The second useful resource will not be activated, so $y_2=0.$ Your entire demand should subsequently be provided by the primary useful resource $y_1=6.$ The operational price is:

$Q(1,0)=2(6)+0=12.$

Including the activation price offers a possible answer to the unique drawback with whole price:

$5(1)+1(0)+12=17.$

The primary possible grasp determination ($bar{x}=(1,0)$) subsequently supplies $UB=17.$ We now have:

$LB=5, qquad UB=17.$

The subproblem is possible, however the grasp estimated an operational price ($theta$) of zero as an alternative of twelve. We should subsequently generate an optimality minimize.

2.6.2 Developing the twin subproblem

Earlier than substituting the present grasp answer, the operational subproblem might be written as:

$Q(x)=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$-y_1geq -6x_1,$

$-y_2geq -4x_2,$

$y_1,y_2geq 0.$

Let ($u_1$) be the twin variable related to the demand constraint, whereas ($u_2$) and ($u_3$) are related to the capability constraints of the primary and second assets. The twin subproblem is:

$max quad 6u_1-6x_1u_2-4x_2u_3$

topic to

$u_1-u_2leq 2,$

$u_1-u_3leq 1,$

$u_1,u_2,u_3geq 0.$

For the present grasp answer ($bar{x}=(1,0)$), the twin goal turns into:

$max quad 6u_1-6u_2$

topic to

$u_1-u_2leq 2,$

$u_1-u_3leq 1,$

$u_1,u_2,u_3geq 0.$

An optimum twin answer is:

$u_1=2, qquad u_2=0, qquad u_3=1.$

The corresponding twin goal worth is:

$6(2)-6(0)=12.$

This matches the primal subproblem worth ($Q(1,0)=12$), as assured by robust duality.

2.6.3 Producing the optimality minimize

We substitute the optimum twin answer into the final twin goal:

$thetageq 6u_1-6x_1u_2-4x_2u_3.$

Utilizing ($u_1=2$), ($u_2=0$), and ($u_3=1$), we get hold of:

$thetageq 6(2)-6x_1(0)-4x_2(1).$

Due to this fact, the optimality minimize is:

$thetageq 12-4x_2.$

On the present answer ($bar{x}=(1,0)$), this minimize requires, $thetageq 12.$

The grasp can not activate solely the primary useful resource whereas pretending that the operational price ($theta$) is zero. The minimize additionally tells the grasp that activating the second useful resource can scale back the operational price as a result of that useful resource provides items extra cheaply.

2.6.4 The ultimate grasp iteration

The grasp drawback now comprises each the feasibility minimize and the optimality minimize:

$min quad 5x_1+x_2+theta$

topic to

$x_1+x_2geq 1,$

$6x_1+4x_2geq 6,$

$thetageq 12-4x_2,$

$thetageq 0,$

$x_1,x_2in{0,1}.$

If solely the primary useful resource is activated, the grasp goal is, $5(1)+1(0)+12=17.$ If each assets are activated, the optimality minimize requires, $thetageq 12-4(1)=8.$ The corresponding grasp goal is:

$5(1)+1(1)+8=14.$

The brand new grasp answer is subsequently:

$bar{x}_1=1, qquad bar{x}_2=1, qquad theta=8.$

The brand new decrease sure is, $LB=14.$

2.6.5 Evaluating the ultimate answer

For ($bar{x}=(1,1)$), the operational subproblem turns into:

$Q(1,1)=min quad 2y_1+y_2$

topic to

$y_1+y_2geq 6,$

$y_1leq 6,$

$y_2leq 4,$

$y_1,y_2geq 0.$

As a result of the second useful resource has the bottom working price, the subproblem makes use of its total capability, $y_2=4.$ The remaining two items are provided by the primary useful resource, $y_1=2.$ The operational price is:

$Q(1,1)=2(2)+4=8.$

Including the activation prices ($5x_1 + x_2$) offers:

$5(1)+1(1)+8=14.$

This possible answer improves the higher sure, $UB=14.$ We now have:

$LB=14, qquad UB=14.$

As a result of the decrease and higher bounds coincide, the algorithm has converged. The optimum answer is:

$x_1^*=1, qquad x_2^*=1, qquad y_1^*=2, qquad y_2^*=4,$

with optimum goal worth $z^*=14.$

The toy instance illustrates the 2 distinct types of suggestions utilized by Benders decomposition. The primary grasp determination produced no possible operational answer, so Farkas’ lemma generated a feasibility minimize that restricted the place the grasp might search. The following determination was possible, however its operational price was underestimated, so the twin subproblem generated an optimality minimize. Collectively, these cuts guided the grasp towards an answer that was each possible and optimum.

3. Making use of feasibility cuts to capacitated facility location

The toy instance confirmed how inadequate useful resource capability could make a Benders subproblem infeasible. The capacitated facility location drawback follows the identical logic on a bigger scale. The grasp decides which services to open, whereas the subproblem determines how buyer demand must be provided by the chosen services.

Not like the uncapacitated drawback studied in Half I, opening no less than one facility doesn’t assure feasibility. The opened services might present inadequate whole capability, or their areas might forestall them from serving specific clients. The algorithm should subsequently generate feasibility cuts at any time when the chosen services can’t help a sound transportation plan.

3.1 The capacitated facility location drawback

Let ($I$) denote the set of candidate services and ($J$) the set of consumers. We use ($Asubseteq Itimes J$) to symbolize the permitted connections between services and clients.

The parameters are:

• ($f_i$): mounted price of opening facility ($i$);
• ($K_i$): capability of facility ($i$);
• ($d_j$): demand of buyer ($j$);
• ($c_{ij}$): price of supplying one unit from facility ($i$) to buyer ($j$).

The binary variable ($x_i$) signifies whether or not facility ($i$) is opened. The continual variable ($y_{ij}$) represents the amount provided from facility ($i$) to buyer ($j$). The entire capacitated facility location mannequin is:

$min quad sum_{iin I} f_i x_i + sum_{(i,j)in A} c_{ij}y_{ij}$

topic to

$sum_{i:(i,j)in A} y_{ij}geq d_j qquad forall jin J,$

$sum_{j:(i,j)in A} y_{ij}leq K_i x_i qquad forall iin I,$

$x_iin{0,1} qquad forall iin I,$

$y_{ij}geq 0 qquad forall (i,j)in A.$

The primary household of constraints requires each buyer’s demand to be happy. The second limits the overall amount provided by every facility to its accessible capability and prevents closed services from serving clients.

3.2 The Benders grasp drawback

The grasp drawback comprises the facility-opening variables and the variable ($theta$), which estimates the transportation price. The preliminary grasp drawback is:

$min quad sum_{iin I} f_i x_i+theta$

topic to

$x_iin{0,1} qquad forall iin I,$

$thetageq 0,$

along with the feasibility and optimality cuts generated throughout the algorithm. Initially, the grasp is aware of little or no concerning the operational penalties of opening a selected mixture of services. It might subsequently choose a reasonable set of services that can’t fulfill all buyer demand.

3.3 The operational subproblem

For a set grasp answer ($bar{x}$), the transportation subproblem is:

$Q(bar{x}) = min_y quad sum_{(i,j)in A} c_{ij}y_{ij}$

topic to

$sum_{i:(i,j)in A} y_{ij}geq d_j qquad forall jin J,$

$sum_{j:(i,j)in A} y_{ij}leq K_ibar{x}_i qquad forall iin I,$

$y_{ij}geq 0 qquad forall (i,j)in A.$

Two outcomes are attainable. If the opened services can fulfill each buyer, the subproblem is possible and returns the minimal transportation price. If the accessible capability or permitted connections are inadequate, the subproblem is infeasible.

3.4 Optimality cuts

To derive the optimality cuts, rewrite the capability constraints as:

$-sum_{j:(i,j)in A} y_{ij} geq -K_ibar{x}_i qquad forall iin I.$

Let ($alpha_jgeq0$) be the twin variable related to the demand constraint of buyer ($j$), and let ($beta_igeq0$) be related to the remodeled capability constraint of facility ($i$).

The twin subproblem is:

$max_{alpha,beta} quad sum_{jin J} d_jalpha_j – sum_{iin I} K_ibar{x}_ibeta_i$

topic to

$alpha_j-beta_ileq c_{ij} qquad forall (i,j)in A,$

$alpha_jgeq0 qquad forall jin J,$

$beta_igeq0 qquad forall iin I.$

When the subproblem is possible, an optimum twin answer ($alpha^ok,beta^ok$) generates the next optimality minimize:

$theta geq sum_{jin J} d_jalpha_j^ok – sum_{iin I} K_ibeta_i^ok x_i.$

This minimize improves the grasp’s approximation of the transportation price related to totally different facility-opening choices.

3.5 Feasibility cuts

If the transportation subproblem is infeasible, we can’t get hold of an operational price or replace the higher sure. As a substitute, Farkas’ lemma supplies multipliers that certify why the chosen services can’t fulfill the operational necessities.

Let ($r_jgeq0$) be the Farkas multiplier related to the demand constraint of buyer ($j$), and let ($s_igeq0$) be related to the remodeled capability constraint of facility ($i$).

A legitimate Farkas certificates satisfies:

$r_j-s_ileq0 qquad forall (i,j)in A,$

$r_jgeq0 qquad forall jin J,$

$s_igeq0 qquad forall iin I,$

and, for the present grasp answer ($bar{x}$),

$sum_{jin J} d_jr_j – sum_{iin I} K_ibar{x}_i s_i >0.$

The ultimate inequality certifies that the present facility-opening determination produces an infeasible transportation system. Any grasp answer that admits a possible subproblem should as an alternative fulfill:

$sum_{jin J} d_jr_j – sum_{iin I} K_i x_i s_i leq0.$

Equivalently, the Benders feasibility minimize is:

$sum_{iin I} K_i s_i x_i geq sum_{jin J} d_jr_j.$

This minimize excludes the present infeasible facility-opening determination and doubtlessly many different choices that will produce the identical capability or connectivity drawback.

When each facility can serve each buyer, one attainable certificates might result in the acquainted total-capacity requirement:

$sum_{iin I} K_i x_i geq sum_{jin J} d_j.$

With restricted facility-customer connections, nevertheless, whole capability will not be ample. Capability should even be accessible at services able to reaching the shoppers that require it. Farkas cuts can seize these extra particular sources of infeasibility.

The entire Benders algorithm subsequently has two branches. If the subproblem is infeasible, it generates a feasibility minimize and returns to the grasp. If the subproblem is possible, it updates the higher sure and generates an optimality minimize. We’ll now implement this whole process in Python utilizing Pyomo and HiGHS.

4. Implementing feasibility cuts with Pyomo and HiGHS

We now have all of the mathematical equipment required to implement the prolonged Benders decomposition algorithm mentioned within the earlier sections. The grasp drawback will choose the services to open, the feasibility subproblem will decide whether or not the ensuing transportation drawback might be operated in any respect, and the twin subproblem will consider its transportation price at any time when a possible operational answer exists.

For instance the whole process, we are going to resolve a small capacitated facility location occasion containing 5 candidate services and twenty clients. The occasion is saved in JSON format in order that the optimization mannequin stays separate from the info and may simply be reused or modified. Each the occasion and the whole pocket book might be downloaded from the accompanying GitHub repository.

The implementation makes use of Pyomo to formulate the optimization fashions and the open-source HiGHS solver to unravel the grasp and subproblems. We’ll first load and put together the info, then assemble the grasp drawback, the auxiliary Farkas drawback used to generate feasibility cuts, and the twin transportation subproblem used to generate optimality cuts. Lastly, we are going to mix these elements into the whole iterative Benders process.

4.1 Loading and making ready the occasion

We start by loading the capacitated facility location occasion straight from the GitHub repository and changing the JSON information into the units and dictionaries that can be used all through the Benders implementation. Along with facility prices, capacities, buyer calls for, and transportation prices, we additionally assemble the service neighborhoods describing which services are allowed to serve every buyer.

!pip -q set up pyomo highspy

import requests
import pandas as pd
import matplotlib.pyplot as plt
import pyomo.environ as pyo

from pyomo.choose import SolverFactory, TerminationCondition

JSON_URL = (
    "https://uncooked.githubusercontent.com/ceche1212/"
    "Benders_Tutorials_TDS/refs/heads/principal/Information/"
    "cflp_benders_5x20_instance.json"
)

occasion = requests.get(JSON_URL, timeout=30).json()

services = [f["id"] for f in occasion["facilities"]]
clients = [c["id"] for c in occasion["customers"]]

fixed_cost = {f["id"]: f["fixed_cost"] for f in occasion["facilities"]}
capability = {f["id"]: f["capacity"] for f in occasion["facilities"]}
demand = {c["id"]: c["demand"] for c in occasion["customers"]}

facility_coordinates = {
    f["id"]: (f["x"], f["y"]) for f in occasion["facilities"]
}
customer_coordinates = {
    c["id"]: (c["x"], c["y"]) for c in occasion["customers"]
}

transportation_cost = {
    (a["facility"], a["customer"]): a["cost_per_unit"]
    for a in occasion["transportation_costs"]
}

arcs = checklist(transportation_cost)

facilities_for_customer = {
    j: [i for i in facilities if (i, j) in transportation_cost]
    for j in clients
}

customers_for_facility = {
    i: [j for j in customers if (i, j) in transportation_cost]
    for i in services
}

assert all(facilities_for_customer[j] for j in clients)

print(f"Services: {len(services)}")
print(f"Prospects: {len(clients)}")
print(f"Transportation arcs: {len(arcs)}")
print(f"Complete demand: {sum(demand.values())}")
print(f"Complete capability: {sum(capability.values())}")

The ensuing information buildings carefully observe the mathematical notation launched earlier. The dictionaries fixed_cost, capability, and demand comprise the parameters ($f_i$), ($K_i$), and ($d_j$), whereas transportation_cost shops ($c_{ij}$) just for permitted facility-customer connections.

The neighborhood dictionaries are notably vital as a result of the transportation community will not be full. facilities_for_customer[j] identifies the services able to serving buyer ($j$), whereas customers_for_facility[i] identifies the shoppers reachable from facility ($i$). For this occasion, the community comprises 5 candidate services, twenty clients, 57 permitted transportation arcs, a complete demand of 49 items, and 89 items of potential capability. Having extra whole capability than demand doesn’t assure feasibility, for the reason that grasp should still open the flawed mixture of services or depart inadequate capability accessible to specific teams of consumers.

4.2 Constructing the preliminary grasp drawback

We are able to now assemble the Benders grasp drawback. As within the mathematical formulation, the binary variables ($x_i$) decide which services are opened, whereas ($theta$) represents the grasp’s present approximation of the transportation price. We additionally create two initially empty constraint lists that may retailer the feasibility and optimality cuts generated all through the algorithm.

Importantly, we intentionally don’t impose any capability or connectivity necessities at this stage. The preliminary grasp is aware of solely the facility-opening prices and that ($theta$) can’t be adverse. The aim of the feasibility cuts can be exactly to show the grasp which combos of services can help a possible transportation plan.

grasp = pyo.ConcreteModel()

grasp.x = pyo.Var(services, area=pyo.Binary)
grasp.theta = pyo.Var(area=pyo.NonNegativeReals)

grasp.FeasibilityCuts = pyo.ConstraintList()
grasp.OptimalityCuts = pyo.ConstraintList()

grasp.TotalCost = pyo.Goal(
    expr=sum(fixed_cost[i] * grasp.x[i] for i in services)
         + grasp.theta,
    sense=pyo.reduce
)

solver = SolverFactory("appsi_highs")

outcomes = solver.resolve(grasp)

if outcomes.solver.termination_condition != TerminationCondition.optimum:
    elevate RuntimeError("The grasp drawback was not solved to optimality.")

x_solution = {
    i: int(spherical(pyo.worth(grasp.x[i])))
    for i in services
}

theta_value = pyo.worth(grasp.theta)
master_objective = pyo.worth(grasp.TotalCost)

print("Preliminary grasp answer:", x_solution)
print(f"Theta: {theta_value:,.2f}")
print(f"Decrease sure: {master_objective:,.2f}")

As a result of the preliminary grasp comprises no Benders cuts, the most cost effective answer is to open no services and set ($theta=0$). The ensuing grasp goal is subsequently zero, offering our first decrease sure.

After all, this answer can’t presumably serve any buyer. That’s intentional. Slightly than manually including constraints that forestall such configurations, we are going to ship the grasp answer to the feasibility subproblem and let Farkas’ lemma generate a minimize explaining why it can’t work. That is the principle distinction with the implementation in Half I, the place the construction of the mannequin assured that each grasp answer produced a possible task subproblem.

4.3 Constructing the normalized Farkas subproblem

The following part is the auxiliary drawback used to detect infeasibility and generate feasibility cuts. For a set grasp answer ($bar{x}$), we seek for nonnegative Farkas multipliers ($r_j$) and ($s_i$) satisfying the circumstances derived earlier. As a result of these multipliers outline a cone, any legitimate certificates might be multiplied by an arbitrary constructive fixed, so we add a normalization constraint to acquire a bounded linear program.

The target measures the violation related to the present grasp answer. If its optimum worth is strictly constructive, the ensuing multipliers present a certificates that the transportation subproblem is infeasible and may instantly be transformed right into a Benders feasibility minimize.

def build_farkas_subproblem(x_bar):
    m = pyo.ConcreteModel()

    m.r = pyo.Var(clients, area=pyo.NonNegativeReals)
    m.s = pyo.Var(services, area=pyo.NonNegativeReals)

    m.FarkasCondition = pyo.Constraint(
        arcs,
        rule=lambda m, i, j: m.r[j] - m.s[i] <= 0
    )

    m.Normalization = pyo.Constraint(
        expr=sum(m.r[j] for j in clients)
           + sum(m.s[i] for i in services) <= 1
    )

    m.CertificateViolation = pyo.Goal(
        expr=sum(demand[j] * m.r[j] for j in clients)
           - sum(capability[i] * x_bar[i] * m.s[i] for i in services),
        sense=pyo.maximize
    )

    return m


farkas = build_farkas_subproblem(x_solution)
outcomes = solver.resolve(farkas)

if outcomes.solver.termination_condition != TerminationCondition.optimum:
    elevate RuntimeError("Farkas drawback was not solved to optimality.")

certificate_value = pyo.worth(farkas.CertificateViolation)

r_solution = {j: pyo.worth(farkas.r[j]) for j in clients}
s_solution = {i: pyo.worth(farkas.s[i]) for i in services}

print(f"Farkas goal: {certificate_value:.6f}")

for j, worth in r_solution.objects():
    if worth > 1e-8:
        print(f"r[{j}] = {worth:.6f}")

for i, worth in s_solution.objects():
    if worth > 1e-8:
        print(f"s[{i}] = {worth:.6f}")

grasp.FeasibilityCuts.add(
    sum(capability[i] * s_solution[i] * grasp.x[i] for i in services)
    >=
    sum(demand[j] * r_solution[j] for j in clients)
)

The constraints ($r_j-s_ileq0$) reproduce the Farkas situation related to each permitted transportation arc. The target then compares the weighted buyer demand with the capability made accessible by the present facility configuration ($bar{x}$).

For the preliminary grasp answer, the optimum goal is constructive, confirming that no possible transportation plan exists. The corresponding values of ($r_j$) and ($s_i$) type the Farkas certificates. We then change the mounted values ($bar{x}_i$) by the grasp variables ($x_i$) and add the ensuing inequality on to grasp.FeasibilityCuts.

The grasp has subsequently obtained its first piece of operational data. As a substitute of merely being advised that its present answer is infeasible, it now receives a constraint describing a household of facility configurations that should be averted.

4.4 Constructing the twin transportation subproblem

As soon as the Farkas drawback confirms that the present facility configuration admits a possible transportation plan, we are able to consider its working price. As in Half I, we do that by way of the twin of the transportation subproblem. The variables ($alpha_j$) are related to the customer-demand constraints, whereas ($beta_i$) correspond to the remodeled facility-capacity constraints.

For a set grasp answer ($bar{x}$), fixing this twin offers the minimal transportation price by way of robust duality. Its optimum multipliers will then be used to generate the standard Benders optimality minimize.

def build_dual_subproblem(x_bar):
    m = pyo.ConcreteModel()

    m.ARCS = pyo.Set(dimen=2, initialize=arcs)

    m.alpha = pyo.Var(clients, area=pyo.NonNegativeReals)
    m.beta = pyo.Var(services, area=pyo.NonNegativeReals)

    m.DualFeasibility = pyo.Constraint(
        m.ARCS,
        rule=lambda m, i, j:
            m.alpha[j] - m.beta[i] <= transportation_cost[i, j]
    )

    m.TransportationCost = pyo.Goal(
        expr=sum(demand[j] * m.alpha[j] for j in clients)
           - sum(capability[i] * x_bar[i] * m.beta[i] for i in services),
        sense=pyo.maximize
    )

    return m

The twin feasibility constraints reproduce the connection ($alpha_j-beta_ileq c_{ij}$) for each permitted transportation arc. The target combines the demand contribution with the capability made accessible by the present grasp answer ($bar{x}$).

Not like the Farkas drawback, this mannequin is used solely after feasibility has been established. Its optimum goal worth offers the transportation price ($Q(bar{x})$), whereas the values of ($alpha_j$) and ($beta_i$) present the coefficients required to assemble an optimality minimize and enhance the grasp’s approximation represented by ($theta$).

4.5 Placing every little thing collectively: the whole Benders loop

We are able to now mix the grasp drawback, the normalized Farkas drawback, and the transportation twin into the whole Benders algorithm. Because the first feasibility minimize has already been added within the earlier subsection, the loop begins by resolving the up to date grasp after which repeatedly determines which kind of suggestions is required.

At every iteration, the grasp supplies a facility configuration and a decrease sure. We first resolve the Farkas drawback. If its goal is constructive, the transportation drawback is infeasible and we add a feasibility minimize. In any other case, we resolve the transportation twin, get hold of a possible whole price and replace the higher sure. If the bounds haven’t but converged, the corresponding twin multipliers generate a brand new optimality minimize.

maximum_iterations = 100
tolerance = 1e-6

lower_bound = -float("inf")
upper_bound = float("inf")
best_solution = None
iteration_results = []

for iteration in vary(1, maximum_iterations + 1):

    # 1. Resolve grasp
    solver.resolve(grasp)
    x_bar = {
        i: int(spherical(pyo.worth(grasp.x[i])))
        for i in services
    }

    theta = pyo.worth(grasp.theta)
    mounted = sum(fixed_cost[i] * x_bar[i] for i in services)
    lower_bound = pyo.worth(grasp.TotalCost)

    # 2. Test feasibility
    farkas = build_farkas_subproblem(x_bar)
    solver.resolve(farkas)
    certificates = pyo.worth(farkas.CertificateViolation)

    if certificates > tolerance:

        r = {j: pyo.worth(farkas.r[j]) for j in clients}
        s = {i: pyo.worth(farkas.s[i]) for i in services}

        grasp.FeasibilityCuts.add(
            sum(capability[i] * s[i] * grasp.x[i] for i in services)
            >= sum(demand[j] * r[j] for j in clients)
        )

        transportation = None
        cut_type = "Feasibility"
        hole = float("inf")

    else:

        # 3. Consider possible answer
        twin = build_dual_subproblem(x_bar)
        solver.resolve(twin)

        transportation = pyo.worth(twin.TransportationCost)
        total_cost = mounted + transportation

        if total_cost < upper_bound:
            upper_bound = total_cost
            best_solution = dict(x_bar)
            best_fixed_cost = mounted
            best_transportation_cost = transportation
            best_total_cost = total_cost

        hole = upper_bound - lower_bound

        # 4. Add optimality minimize if wanted
        if hole <= tolerance:
            cut_type = "None (converged)"
        else:
            alpha = {j: pyo.worth(twin.alpha[j]) for j in clients}
            beta = {i: pyo.worth(twin.beta[i]) for i in services}

            grasp.OptimalityCuts.add(
                grasp.theta >=
                sum(demand[j] * alpha[j] for j in clients)
                - sum(
                    capability[i] * beta[i] * grasp.x[i]
                    for i in services
                )
            )

            cut_type = "Optimality"

    iteration_results.append({
        "iteration": iteration,
        "open services": ", ".be part of(
            i for i in services if x_bar[i]
        ) or "None",
        "theta": theta,
        "Farkas goal": certificates,
        "transportation price": transportation,
        "minimize added": cut_type,
        "decrease sure": lower_bound,
        "higher sure": upper_bound
    })

    print(
        f"{iteration:2nd} | "
        f"open={[i for i in facilities if x_bar[i]]} | "
        f"minimize={cut_type} | "
        f"LB={lower_bound:,.2f} | "
        f"UB={upper_bound:,.2f}"
    )

    if certificates <= tolerance and hole <= tolerance:
        break

print("nFinal Benders answer")
print(f"Open services: {[i for i in facilities if best_solution[i]]}")
print(f"Fastened price: {best_fixed_cost:,.2f}")
print(f"Transportation price: {best_transportation_cost:,.2f}")
print(f"Complete price: {best_total_cost:,.2f}")

As soon as the code finishes operating, we are able to see it converges on iteration 10, acquiring the minimal price.

----------------------------------------------------------------------
Iteration: 1
Open services: ['F2', 'F4']
Fastened price: 4,300.00
Theta: 0.00
Farkas goal: 1.500000
Lower added: Feasibility
Decrease sure: 4,300.00
Precise transportation price: infeasible
Higher sure: not accessible but
Relative hole: not accessible but
----------------------------------------------------------------------
Iteration: 2
Open services: ['F4', 'F5']
Fastened price: 4,400.00
Theta: 0.00
Farkas goal: 1.250000
Lower added: Feasibility
Decrease sure: 4,400.00
Precise transportation price: infeasible
Higher sure: not accessible but
Relative hole: not accessible but
----------------------------------------------------------------------
Iteration: 3
Open services: ['F2', 'F5']
Fastened price: 4,500.00
Theta: 0.00
Farkas goal: 2.000000
Lower added: Feasibility
Decrease sure: 4,500.00
Precise transportation price: infeasible
Higher sure: not accessible but
Relative hole: not accessible but
----------------------------------------------------------------------
Iteration: 4
Open services: ['F2', 'F4', 'F5']
Fastened price: 6,600.00
Theta: 0.00
Farkas goal: -0.000000
Lower added: Optimality
Decrease sure: 6,600.00
Precise transportation price: 8,946.00
Higher sure: 15,546.00
Relative hole: 57.545349%
----------------------------------------------------------------------
Iteration: 5
Open services: ['F1', 'F3', 'F4', 'F5']
Fastened price: 9,300.00
Theta: 0.00
Farkas goal: -0.000000
Lower added: Optimality
Decrease sure: 9,300.00
Precise transportation price: 5,457.00
Higher sure: 14,757.00
Relative hole: 36.979061%
----------------------------------------------------------------------
Iteration: 6
Open services: ['F2', 'F3', 'F4', 'F5']
Fastened price: 9,100.00
Theta: 2,194.00
Farkas goal: -0.000000
Lower added: Optimality
Decrease sure: 11,294.00
Precise transportation price: 5,853.00
Higher sure: 14,757.00
Relative hole: 23.466829%
----------------------------------------------------------------------
Iteration: 7
Open services: ['F1', 'F2', 'F4', 'F5']
Fastened price: 9,000.00
Theta: 2,826.00
Farkas goal: -0.000000
Lower added: Optimality
Decrease sure: 11,826.00
Precise transportation price: 6,497.00
Higher sure: 14,757.00
Relative hole: 19.861761%
----------------------------------------------------------------------
Iteration: 8
Open services: ['F3', 'F4', 'F5']
Fastened price: 6,900.00
Theta: 5,853.00
Farkas goal: 0.666667
Lower added: Feasibility
Decrease sure: 12,753.00
Precise transportation price: infeasible
Higher sure: 14,757.00
Relative hole: inf%
----------------------------------------------------------------------
Iteration: 9
Open services: ['F1', 'F2', 'F3', 'F4', 'F5']
Fastened price: 11,500.00
Theta: 2,055.00
Farkas goal: -0.000000
Lower added: Optimality
Decrease sure: 13,555.00
Precise transportation price: 4,208.00
Higher sure: 14,757.00
Relative hole: 8.145287%
----------------------------------------------------------------------
Iteration: 10
Open services: ['F1', 'F3', 'F4', 'F5']
Fastened price: 9,300.00
Theta: 5,457.00
Farkas goal: -0.000000
Lower added: None (converged)
Decrease sure: 14,757.00
Precise transportation price: 5,457.00
Higher sure: 14,757.00
Relative hole: 0.000000%

Benders decomposition converged.

======================================================================
Last Benders answer
======================================================================
Facility F1: Open (capability = 18)
Facility F2: Closed (capability = 20)
Facility F3: Open (capability = 16)
Facility F4: Open (capability = 18)
Facility F5: Open (capability = 17)

Fastened opening price: 9,300.00
Transportation price: 5,457.00
Complete price: 14,757.00
Iterations after the primary feasibility minimize: 10

The central distinction with Half I is the conditional step instantly after fixing the grasp. A constructive Farkas goal signifies that the present facility configuration can’t help a possible transportation plan, so no higher sure might be computed and the algorithm provides a feasibility minimize as an alternative. As soon as the Farkas goal falls to zero, the transportation drawback is possible and the algorithm switches to the acquainted optimality-cut mechanism.

The grasp goal supplies the decrease sure all through the process, whereas each possible facility configuration supplies a candidate higher sure. The loop terminates solely when a possible subproblem is obtained and these two bounds coincide inside the prescribed tolerance. We additionally retailer the principle data from each iteration in order that we are able to examine how the feasibility and optimality cuts progressively information the grasp towards the optimum.

4.6 Recovering and visualizing the ultimate answer

The Benders algorithm offers us the optimum facility-opening choices and transportation price, however the twin subproblem doesn’t straight present the precise buyer flows ($y_{ij}$). We subsequently resolve the unique transportation subproblem one ultimate time with the optimum facility configuration mounted. This recovers the flows used within the ultimate answer, which we are able to then visualize along with the open and closed services.

As a further validation, the whole pocket book additionally solves the unique monolithic capacitated facility location mannequin and confirms that its goal worth matches the Benders answer.

# Recuperate the primal transportation answer
transport = pyo.ConcreteModel()
transport.y = pyo.Var(arcs, area=pyo.NonNegativeReals)

transport.Demand = pyo.Constraint(
    clients,
    rule=lambda m, j:
        sum(m.y[i, j] for i in facilities_for_customer[j]) >= demand[j]
)

transport.Capability = pyo.Constraint(
    services,
    rule=lambda m, i:
        sum(m.y[i, j] for j in customers_for_facility[i])
        <= capability[i] * best_solution[i]
)

transport.Value = pyo.Goal(
    expr=sum(
        transportation_cost[i, j] * transport.y[i, j]
        for i, j in arcs
    ),
    sense=pyo.reduce
)

solver.resolve(transport)

flows = {
    (i, j): pyo.worth(transport.y[i, j])
    for i, j in arcs
    if pyo.worth(transport.y[i, j]) > 1e-6
}

print(f"Transportation price: {pyo.worth(transport.Value):,.2f}")
print(f"Complete price: {best_total_cost:,.2f}")


# Plot the answer
fig, ax = plt.subplots(figsize=(12, 8))

max_flow = max(flows.values())

for (i, j), circulation in flows.objects():
    xi, yi = facility_coordinates[i]
    xj, yj = customer_coordinates[j]
    ax.plot(
        [xi, xj], [yi, yj],
        linewidth=1 + 2 * circulation / max_flow,
        alpha=0.5
    )

ax.scatter(
    *zip(*(customer_coordinates[j] for j in clients)),
    s=70, label="Prospects"
)

open_facilities = [i for i in facilities if best_solution[i]]
closed_facilities = [i for i in facilities if not best_solution[i]]

ax.scatter(
    *zip(*(facility_coordinates[i] for i in open_facilities)),
    marker="*", s=350, label="Open services"
)

ax.scatter(
    *zip(*(facility_coordinates[i] for i in closed_facilities)),
    marker="X", s=150, alpha=0.45, label="Closed services"
)

for j in clients:
    ax.annotate(
        f"{j}nd={demand[j]}",
        customer_coordinates[j],
        xytext=(5, 5),
        textcoords="offset factors",
        fontsize=8
    )

for i in services:
    ax.annotate(
        i, facility_coordinates[i],
        xytext=(7, 7),
        textcoords="offset factors",
        fontweight="daring"
    )

ax.set(
    title="Optimum Capacitated Facility Location Answer",
    xlabel="X coordinate",
    ylabel="Y coordinate"
)
ax.set_aspect("equal")
ax.grid(alpha=0.25)
ax.legend()
plt.tight_layout()
plt.present()

The ultimate transportation mannequin fixes the ability choices obtained by Benders and optimizes solely the continual flows. We retain the constructive ($y_{ij}$) values and use them to attract the energetic transportation connections, with thicker strains representing bigger flows.

For this occasion, the optimum answer opens services F1, F3, F4, and F5, whereas F2 stays closed. The ultimate goal worth is 14,757, combining 9,300 in facility-opening prices with 5,457 in transportation prices. Fixing the unique monolithic CFLP within the full pocket book produces precisely the identical goal worth, offering a helpful numerical verify that the Benders implementation has converged to the proper optimum.

Conclusions

On this second article, we prolonged the classical Benders decomposition framework to conditions during which the grasp can suggest choices that make the operational subproblem infeasible. Utilizing a capacitated facility location drawback, we noticed how Farkas’ lemma supplies a certificates of infeasibility and the way this certificates might be remodeled right into a Benders feasibility minimize.

This distinction is vital. An optimality minimize tells the grasp {that a} possible determination is dearer than it presently believes. A feasibility minimize tells the grasp {that a} determination can’t work in any respect. Extra importantly, the Farkas certificates permits us to establish a few of the structural necessities that possible options should fulfill, so a single minimize can doubtlessly remove many grasp options that will result in the identical operational impossibility.

There’s, nevertheless, one other method of excluding infeasible integer options. If we merely need to forestall the grasp from deciding on a selected discrete answer once more, we are able to use a no-good minimize. Not like the Farkas cuts studied right here, a no-good minimize doesn’t essentially clarify the structural motive for infeasibility. It could possibly merely take away a selected mixture of integer choices from the search house. This will likely sound much less subtle, nevertheless it turns into notably helpful when the subproblem itself is not a linear program.

To date, our decomposition has adopted a really handy construction. The troublesome integer variables stay within the grasp, whereas fixing them leaves a steady linear subproblem. When that LP is possible, its twin variables present the optimality cuts. When it’s infeasible, Farkas’ lemma supplies the feasibility cuts. In each instances, LP duality offers us the mathematical suggestions required by the grasp.

However what occurs when fixing the grasp variables nonetheless leaves an integer or mixed-integer optimization drawback? In that case, there may be typically no LP twin answer that we are able to use to assemble the classical Benders optimality cuts developed within the first two articles.

That is the place Logic-Based mostly Benders Decomposition enters the image. As a substitute of deriving each minimize from linear programming duality, we use the construction and logic of the subproblem itself to speak helpful data again to the grasp. No-good cuts are one of many easiest instruments accessible on this setting, though stronger problem-specific cuts are often much more priceless.

That would be the topic of the following article on this collection. We’ll transfer from facility location to a parallel-machine scheduling drawback with sequence-dependent setup occasions (a troublesome optimization drawback, that seems loads in manufacturing and manufacturing)” . The grasp will determine how jobs are assigned to machines, however figuring out the most effective sequence of jobs on every machine will stay a combinatorial optimization drawback. This may pressure us to go away the snug world of LP duality and assemble Benders cuts utilizing a distinct type of reasoning.

I sincerely hope you discovered this text helpful and that feasibility cuts and Farkas’ lemma now really feel rather less mysterious.

You can even observe the newest work from Sávila Training and join with me on LinkedIn. All of the code and information used on this article might be discovered within the accompanying GitHub repository.

Thanks for taking the time to learn. See you in Half III.