# A Hybrid Approach of Bundle and Benders Applied Large  Mixed Linear Integer Problem

Authors: Placido Rogerio Pinheiro; Paulo Roberto Oliveira
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Consider a large mixed integer linear problem where structure of the constraint matrix is sparse, with independent blocks, and coupling constraints and variables. There is one of the groups of constraints to make difficult the application of Benders scheme decomposition. In this work, we propose the following algorithm; a Lagrangian relaxation is made on the mentioned set of constraints; we presented a process heuristic for the calculation of the multiplier through the resolution of the dual problem, structured starting from the bundle methods. According to the methodology proposed, for each iteration of the algorithm, we propose Benders decomposition where quotas are provided for the value function andε-subgradient.


---

## Body

## 1. Introduction

The main objective of this work is to develop a methodology that combines the Benders decomposition and a heuristic for calculating the multiplier applied to a relaxed problem to solve a linear problem of large integer(1)minctx+dty,s.t.Ax+By≤b,x∈XR,y∈Y,
where XR={x:Dx≤d,x≥0} and Y={y:Fy≤f,y≥0,yinteger}.Relaxing a part of the restrictions has been updated by multiplying the respective heuristic process, solving a local model of dual relaxed. As the algorithm presented, for each iteration with the multiplier obtained, apply iterations of Benders decomposition on the relaxed problem, obtaining anε-subgradient quotas and lower and upper optimal solution. The motivation of this work arises from an integer linear problem from the large expansion planning of the transmission of a digital telecommunication system in an urban area equivalent to a city the size of Rio de Janeiro/Brazil [1]. Section 2 gives an outline about decomposition methods for large scale, with all the relevant features for this work. Moreover, Section 3 shows the integer linear model in this work. More details of the methodology regularization and Benders decomposition are given in Section 4. Section 5 gives an improvement the Approximate Algorithm Bundle. In Section 6 is presented some conclusion and future works obtained from this work.


## 2. Decomposition Methods for Large Scale

The large mixed integer linear programming problem has highlighted the difficulty to be solved directly through commercial software. In such cases the Lagrangian, combined with subgradient optimization, is often used to lower levels to find the optimal value of the objective function. These quotes can be used, for example, the method of Branch-and-Bound [2], or just to measure the quality of feasible solutions. These properties are currently incorporated in commercial software [3]. Other strategies are also considered: obtaining upper bounds [4], more efficient routines on the generation of cuts and the use of parallel processing [5]. The Lagrangian was used by [6, 7] with its work on the traveling salesman problems, and methods of Branch-and-Bound and implicit enumeration had considerable gain in [8] with the Lagrangian, in [9]. There are several questions directed to the Lagrangian in integer linear problems, among them how to calculate the Lagrange multipliers, how to choose among the various relaxations of the problem, and how to obtain viable solutions to the primal problem. Techniques for solving the Lagrangian dual relaxation of combinatorial optimization problems in polynomial time by applying the algorithm as a subroutine of ellipsoids [10] have been presented with [11]. Other methodologies use heuristics decomposition lagrange combining the solution of the Lagrangian Dual by the method of subgradient, also considering the feasible solutions primal heuristics [12]. These techniques were applied to flow problems in networks “multicommodity” in [13], the capacitated location problems [14]. The decomposition Benders [15] is an exact method, finite, effective when the number of integer variables is much smaller than the number of continuous variables in which case the master problem has dimension much smaller than the original problem. However, for large problems, the Benders master problem can be difficult to solve because of the large size. It joins the convergence speed generally slow, making this method inefficient in many cases. Moreover, computational experiments have shown that a general code of Branch-and-Bound applied to solve the problem Benders master produces a tree often much larger than for solving the original problem. Thus, the disadvantage of this decomposition is often the difficulty in solving the master problem, making it inefficient.Several papers were presented with the objective of solving the problem about master with a higher overall efficiency. Among these, [2, 9, 13, 21, 56, 62] implement the Benders decomposition with Lagrangian applied in cuts master problem. [22–25]. This transfers the difficulty of the master problem in solving iteratively the maximum dual function. In [26, 27] this method is denied due to lack of controllability (the optimal solution in the Benders master problem can never achieve the optimum in relaxed master problem) in the solution of the relaxed master problem. There are also suggestions on how to get a good initial set of cuts for the Benders master problem [28, 29]. In [30] suggests the use of linear relaxation for the Benders master problem in a number of initial iterations.Motivated by these failures, [31, 32] developed the “Cross Decomposition” while exploiting the structures of primal and dual problems, combining the advantages of Dantzig-Wolfe decomposition [33, 34] and Benders [34, 35]. Reference [27] carried out a comparative study of several approaches to the problem Benders master, presenting an efficient method for solving a linear problem, the whole “Cross Decomposition” [31, 32, 36–39]. Theoretical aspects of Benders decomposition together with the “Cross Decomposition” are also discussed in [36, 40]. Changes in “Cross Decomposition” for integer linear programming problems were made by [13, 37]. These changes are made through the generalization of the method of Kornai and Liptak [41], which eliminates the need to use the master primal and dual problems. The dynamics of this decomposition is the subproblems, which iterates the primal and dual subproblems. Instead of using the last sub-problem solution as input to another, using an average of all previous subproblem solutions. The convergence proof of this methodology is found in [42]. For a certain class of location problems are presented structured exact solution methods from the “Cross Decomposition” in [36, 40, 43]. A comparison of techniques Kornai and Liptak for Decomposition and Cross-linear problems with block-angular structures and computational results is discussed in [16, 44]. Both methodologies have also been applied to problems of organizational planning [45]. Reference [46] presented a simplified algorithm of “Cross Decomposition” for multiple-choice right-side constraints. Applications involving stochastic transport problems were addressed in [47], involving comparative study with other methods.The update of the multipliers can be made by various methods. If formulated as a linear problem, the simplex is traditionally used. Moreover, in general, a dual nondifferentiable and classical approach is the method of subgradient  [1, 23–25, 48], which is known not to be a method of lowering. Although more complex, the techniques originally developed for bundle [49–51] are being increasingly used. The method exploits bundle data from previous iterations, vectors iterated, objective function, and subgradients, the bundle information, to produce new iteration. The method of ε-descend [52] considers the method of programming differentiable subgradient conjugates [49, 50]. Kiwiel in [53–55] provides new insight into the method of Bundle based on classical methods of cutting planes developed by [56, 57]. The basic idea of generalization of cutting planes is to add a quadratic regularization to the linear approximation by convex parts to the objective function; this linearization is generated by using the subgradient. To avoid a large bundle, it is necessary to limit it. Reference [58], for example, presented a selection strategy based on the subgradient multipliers associated with the local model, where the bundle that remains in subgradient n+2, n being the size of a variable of the problem, considered three approaches to specify the quadratic stabilization process, which are essentially equivalent. The first technique uses the confidence regions; see [59, 60]. The Moreau-Yosida regularization generates the proximal method used by [61]. A modern synthesis technique using bundle and metric variable is made ​​from the concept of Moreau-Yosida regularization in [62, 63]. Applications in control problems involving the method of bundle can be found in [64], and other applications using Lagrangian decomposition, networks, and comparative tests with other algorithms are developed in [60] and decompositions of large and parallel optimization in [65]. Lemarechal according to [66] “is not an exaggeration to say that 90 percent of the applications of nondifferentiability appear in decompositions of one form or another, while the remaining 10 percent are shown via the calculation of eigenvalues.” We mention also [67] when C. Lemaréchal says, “the nondifferentiable optimization has the biggest deficiency of the speed of convergence.”


## 3. Model

Consider the integer linear problem(P), motivated by an application in a telecommunications system [1], as follows:
(P)νP=min∑k=14cktxk+∑j=12ejtyj,s.t.Dkxk=dk,k=1,…,4,Fjyj≤fj,j=1,2Akxk+Bky1=Kk,k=1,…,4,C3x3+C4x4+C2y2=K5,xk≥0,yj≥0integer,k=1,…,4j=1,2,
where the matrices Ak,Bk,C2,C3,C4,Dk and Fj have appropriate dimensions with the vectors ck,dk,ej,fj,Kk,K5,xk  and yj.On the other hand, considerX=∏k=14Xk where Xk={xk;Dkxk-dk=0∧xk≥0,xkintegers} and Y=∏j=12Yj where Yj={yj;Fjyj-fj≤0∧yj≥0,yjintegers}, supposed nonempty and limited, that is finite.Consider the integer linear programming problem(P):
(ILP)νPI=min∑k=14cktxk+∑j=12ejtyj,s.t.Akxk+Bky1=Kk,k=1,…,4,s.t.C3x3+C4x4+C2y2=K5,s.t.x∈X,y∈Y.
A relaxation of the continuous variable x(ILP) generates (ILPx):
(ILPx)νP=min∑k=14cktxk+∑j=12ejtyj,s.t.Akxk+Bky1=Kk,k=1,…,4,s.t.C3x3+C4x4+C2y2=K5,s.t.x∈XR,y∈Y,
where XR=∏k=14X(k)R, and  X(k)R={xk;Dkxk-dk=0∧xk≥0}.Also to relax the variabley  (ILPy) is obtained is follows:
(ILPy)νPR=min∑k=14cktxk+∑j=12ejtyj,s.t.Akxk+Bky1=Kk,k=1,…,4,s.t.C3x3+C4x4+C2y2=K5,s.t.x∈XR,y∈YR,
where  Y(j)={yj;Fjyj-fj≤0∧yj≥0}.Relaxing the last block of constraints(ILP), we have the dual
(DI)vDI=maxλφ(λ),
where for all λ defines the dual function. 						(φ)φ(λ)=min(x,y)∈WIℓ(x,y,λ)=min∑k=14cktxk+∑j=12ejtyj+λt(C3x3+C4x4+C2y2-K5),s.t.(x,y)∈WI,
where WI={(x,y);x∈XR,y∈Y,Akxk+Bky1=Kk,k=1,…,4}.The purpose of this relaxation is to ensure separability of blocks of variablesx3 and x4, y2 over in order, then applying the Benders decomposition.


## 4. Methodology Regularization and Benders Decomposition

The slow convergence of the algorithms in structured Benders decomposition applied large-scale integer linear programming problems motivated the development of the methodology to accelerate the classical method. Applies to Benders decomposition to the large-scale integer linear programming problem with a Lagrangian relaxation, to update the Lagrange multipliers by a Bundle Methods.


### 4.1. Benders Decomposition for the Relaxed Problem

The Benders decomposition applied to the relaxed problem(φ) is to reformulate this problem in an equivalent containing only y-integer variables and a continuous variable. Without loss of generality, assume that the problem has a finite optimal solution for all λ.For eachλ, (φ) can be rewritten as:
(φ′)miny∈Q{∑j=12ejtyj+λtC2y2+min{∑k=14cktxk+λt(C3x3+C4x4),Akxk=Kk-Bky1,k=1,…,4,x∈XR∑k=14cktxk}∑j=12ejtyj},
where Q={y∈Y;∃x∈XRsuchthatAkxk=Kk-Bky1k=1,…,4}, nonempty.Fory∈Q with y1 fixed, the inner minimization subproblem (with explicit XR)
(L)vL=minx∑k=14cktxk+λt(C3x3+C4x4),s.t.Dkxk=dk,k=1,…,4,s.t.Akxk=Kk-Bky1,k=1,…,4,s.t.xk≥0,k=1,…,4
has given its dual
(D)vD=max(v,u)∑i=14ditvi+∑i=14(Ki-Biy1)tui,s.t.Ditvi+Aitui≤c~iwherec~i={ci,i=1,2,ci+Citλ,i=3,4,
where u=(u1,…,u4)t and v=(v1,…,v4)t.We assume that the polyhedral(2)U(λ)={(v,u);Ditvi+Aitui≤c~iwherec~i={ci,i=1,2,ci+Citλ,i=3,4}
are uniformly bounded, if necessary adding dimensions to variables (v,u) and λ.Thus we can define the set{(vq,uq)λ} for all q∈PU(λ) (finite) of extreme points of U(λ). In this case, (φ′) is equal to
(φ1)miny∈Q{∑j=12ejtyj+λtC2y2+maxq∈PU(λ){∑i=14ditviq+∑i=14(Ki-Biy1)tuiq}}.
Consider that zL(λ), the argument of the minimum, has for any subset PU(λ)′⊆PU(λ), the relaxed Benders master problem:
(MB)zL(λ)=min(z,y)z,s.t.z≥∑j=12ejtyj+∑i=14ditviq+∑i=14(Ki-Biy1)tuiq,z∈ℝ,y∈Y,∀q∈PU(λ)′.


### 4.2. Quotas

Forλ fixed, consider  zU(λ)=∑j=12ejtyj+λtC2y2+vD upper limit, where vD was obtained in relaxed primal dual subproblem (D) and zL(λ) was obtained in relaxed primal dual subproblem (MB).Then(3)zL(λ)≤φ(λ)=min(x,y)∈WIℓ(x,y,λ)≤zU(λ).
For λ variable, if we assume that, as done in the algorithm, the restrictions relaxed Benders master problem will remain the same from one to another iteration in λ, then zL(λp+1)≥zL(λp).


### 4.3. Regularization Dual Quadratic Problem

The iterative solution of the dual problem of maximizing intoφ(DI), that updates the multiplier λ, is done using a local regulated model, such as the Bundle. However we do not know for each λ, the value of φ(λ), we only have lower quotas zL(λ) and upper zU(λ).Suppose that we are in thepth iteration λp. Consider the model
(FI)w(λp)=max(w,ρ)w-12tp∥ρ-λp∥2,s.t.w≤(gr)t(ρ-λp)+zU(ρr),r≥1,
where tp>0, which determines the size of direction ρ-λP.For application of the Bundle method, consider the following.(a)
The value ofgr≔C3x3r+C4x4r+C2y2r-K5 corresponds to some εr-subgradient of φ in  λr.Indeed, for(xr,yr)∈WI and any λp,
(4)φ(λp)=min(x,y)∈WIℓ(x,y,λp)=ℓ(xr,yr,λp)-εr,forsomeεr≥0Definingℓ,
(5)φ(λp)=(λp-λ)tgr+ℓ(xr,yr,λ)-εr≥(λp-λ)tgr+φ(λ)-εr,
that is, gr∈∂εrφ(λp) (subdifferencial of  φ(λp)).(b)
The linear cuts, corresponding to the local polyhedral model, and alsoφ(λr). This value is replaced by the upper bound zU(ρr), provided by the primal relaxed dual subproblem (D). To get gr, zU(ρr),  zL(ρr) may require a few iterations of the Benders algorithm.Indeed, consider acceptable(gr,zU(ρr),zL(ρr))  if test quality of the approximation of φ(ρr) is verified as follows:
(6)zU(ρr)-zL(ρr)≤α(zU(λp-1)-zL(λp-1)),forsome0<α<1.It is noted that the convergence Benders method ensures that the test will be checked in a finite number of iterations [15]. With this test it is ensured that the maximum error in calculating φ, from one iteration to another in λ, decreases. Indirectly we also expect  εr→0.With this set of information, we have the model “approximate”(7)Ωp(ρ):=minr{(gr)t(ρ-λp)+zU(ρr)}.Thus, equivalently,(FI) is as follows:
(8)maxρ{Ωp(ρ)-12tp∥ρ-λp∥2}.
The regularized model (FI) has embedded in it the process (decomposed) plans secants and intends to determine a direction of ascent through the accumulated residue, with the approximate calculation of the dual function φ(λ) in (DI), through Benders decomposition. The lemma and the proposition that follow seek to justify the existence and uniqueness of the solution of the quadratic subproblem, like it’s the aggregate subgradient.Lemma 1 (see LemmaXV.3.1.1 in [69]).
The problem (8) has a unique solution ρp+1 characterized by
(9)ρp+1=λp+tpg^p,g^p∈∂Ωp(ρp+1).
Furthermore
(10)Ω(λ)≤zL(λp)+(g^p)t(λ-λp)+e^p,∀λ,
where
(11)e^p=Ω(ρp+1)-zL(λp)-tp∥g^p∥2.Proof.
Suppose nonempty set generated by linear constraints, the existence and uniqueness of the solutionρp+1 following the definition of a positive quadratic. The optimality condition for this solution is
(12)0∈∂Ωp(ρp+1)-1tp(ρp+1+λp).
Then(13)Ω(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)
which is equivalent to
(14)Ω(λ)≤zL(λp)+(g^p)t(λ-λp)-zL(λp)+Ω(ρp+1)+(g^p)t(λp-ρp+1).
Considering (9) recognizes the expression (11) of e^p.Proposition 2 (see LemmaXV.3.1.2 in [69]).
With the notation of Lemma1, consider a quadratic function Ψ:ℝn→ℝ∪{∞} satisfying
(15)Ψ(λ)≤zL(λp)+(g^p)t(λ-λp)+e^p=:φ~(λ),∀λ,
where equality in λ=ρp+1. Then ρp+1 maximizes the function
(16)Ψ~(λ)≔Ψ(λ)+12tp∥λ-λp∥2.Proof.
Applying (9) and (11) and defining relations Ψ can be written as follows:
(17)Ψ(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)-Ω(ρp+1)+(g^p)t(ρp+1-λp)+zL(λp)+e^p,∴Ψ(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)
with equality in λ=ρp+1. Subtracting the term (1/tp)(λ-λp)=0 both sides,
(18)Ψ~(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)-12tp∥λ-λp∥2,
even with equality  λ=ρp+1. Now note that the function of the right side is maximized when
(19)g^p-1tp(λ-λp)=0,
corresponding to ρp+1, given by (9).The functionφ~(λ) is known to aggregate linearization approximation of φ, where the limit on the model Ω, as described in Lemma 1.A more convenient way to solve(FI) is to be made through the dual problem. Define the Lagrangian and their optimality conditions as follows:Ford:=ρ-λp,
(20)ℓ*(w,d,η)=w-12tp∥d∥2-∑r∈{1,…,ℓ)ηr(w-(gr)td-zU(ρr)),η≥0ℓw*=0∴∑r∈{1,…,ℓ)ηr=1,ℓd*=0∴-12tpd+∑r∈{1,…,ℓ)ηrgr=0.
Complementarity,
(21)ηr[w-(gr)td-zU(ρr)]=0,r≥1.
Substituting these equations into ℓ*, it has the following quadratic linear problem:
(DFI)min℘(η),s.t.∑r∈{1,…,ℓ)ηr=1,s.t.ηr≥0,
where
(22)℘(η)=tp2∥∑r∈{1,…,ℓ)ηrgr∥2+∑r∈{1,…,ℓ)ηrzU(ρr).Consider that the optimality conditions have also to update the multiplier(23)ρ=λp+tp(∑r∈{1,…,ℓ)ηrgr),
where η is single solution of (DFI).


## 4.1. Benders Decomposition for the Relaxed Problem

The Benders decomposition applied to the relaxed problem(φ) is to reformulate this problem in an equivalent containing only y-integer variables and a continuous variable. Without loss of generality, assume that the problem has a finite optimal solution for all λ.For eachλ, (φ) can be rewritten as:
(φ′)miny∈Q{∑j=12ejtyj+λtC2y2+min{∑k=14cktxk+λt(C3x3+C4x4),Akxk=Kk-Bky1,k=1,…,4,x∈XR∑k=14cktxk}∑j=12ejtyj},
where Q={y∈Y;∃x∈XRsuchthatAkxk=Kk-Bky1k=1,…,4}, nonempty.Fory∈Q with y1 fixed, the inner minimization subproblem (with explicit XR)
(L)vL=minx∑k=14cktxk+λt(C3x3+C4x4),s.t.Dkxk=dk,k=1,…,4,s.t.Akxk=Kk-Bky1,k=1,…,4,s.t.xk≥0,k=1,…,4
has given its dual
(D)vD=max(v,u)∑i=14ditvi+∑i=14(Ki-Biy1)tui,s.t.Ditvi+Aitui≤c~iwherec~i={ci,i=1,2,ci+Citλ,i=3,4,
where u=(u1,…,u4)t and v=(v1,…,v4)t.We assume that the polyhedral(2)U(λ)={(v,u);Ditvi+Aitui≤c~iwherec~i={ci,i=1,2,ci+Citλ,i=3,4}
are uniformly bounded, if necessary adding dimensions to variables (v,u) and λ.Thus we can define the set{(vq,uq)λ} for all q∈PU(λ) (finite) of extreme points of U(λ). In this case, (φ′) is equal to
(φ1)miny∈Q{∑j=12ejtyj+λtC2y2+maxq∈PU(λ){∑i=14ditviq+∑i=14(Ki-Biy1)tuiq}}.
Consider that zL(λ), the argument of the minimum, has for any subset PU(λ)′⊆PU(λ), the relaxed Benders master problem:
(MB)zL(λ)=min(z,y)z,s.t.z≥∑j=12ejtyj+∑i=14ditviq+∑i=14(Ki-Biy1)tuiq,z∈ℝ,y∈Y,∀q∈PU(λ)′.


## 4.2. Quotas

Forλ fixed, consider  zU(λ)=∑j=12ejtyj+λtC2y2+vD upper limit, where vD was obtained in relaxed primal dual subproblem (D) and zL(λ) was obtained in relaxed primal dual subproblem (MB).Then(3)zL(λ)≤φ(λ)=min(x,y)∈WIℓ(x,y,λ)≤zU(λ).
For λ variable, if we assume that, as done in the algorithm, the restrictions relaxed Benders master problem will remain the same from one to another iteration in λ, then zL(λp+1)≥zL(λp).


## 4.3. Regularization Dual Quadratic Problem

The iterative solution of the dual problem of maximizing intoφ(DI), that updates the multiplier λ, is done using a local regulated model, such as the Bundle. However we do not know for each λ, the value of φ(λ), we only have lower quotas zL(λ) and upper zU(λ).Suppose that we are in thepth iteration λp. Consider the model
(FI)w(λp)=max(w,ρ)w-12tp∥ρ-λp∥2,s.t.w≤(gr)t(ρ-λp)+zU(ρr),r≥1,
where tp>0, which determines the size of direction ρ-λP.For application of the Bundle method, consider the following.(a)
The value ofgr≔C3x3r+C4x4r+C2y2r-K5 corresponds to some εr-subgradient of φ in  λr.Indeed, for(xr,yr)∈WI and any λp,
(4)φ(λp)=min(x,y)∈WIℓ(x,y,λp)=ℓ(xr,yr,λp)-εr,forsomeεr≥0Definingℓ,
(5)φ(λp)=(λp-λ)tgr+ℓ(xr,yr,λ)-εr≥(λp-λ)tgr+φ(λ)-εr,
that is, gr∈∂εrφ(λp) (subdifferencial of  φ(λp)).(b)
The linear cuts, corresponding to the local polyhedral model, and alsoφ(λr). This value is replaced by the upper bound zU(ρr), provided by the primal relaxed dual subproblem (D). To get gr, zU(ρr),  zL(ρr) may require a few iterations of the Benders algorithm.Indeed, consider acceptable(gr,zU(ρr),zL(ρr))  if test quality of the approximation of φ(ρr) is verified as follows:
(6)zU(ρr)-zL(ρr)≤α(zU(λp-1)-zL(λp-1)),forsome0<α<1.It is noted that the convergence Benders method ensures that the test will be checked in a finite number of iterations [15]. With this test it is ensured that the maximum error in calculating φ, from one iteration to another in λ, decreases. Indirectly we also expect  εr→0.With this set of information, we have the model “approximate”(7)Ωp(ρ):=minr{(gr)t(ρ-λp)+zU(ρr)}.Thus, equivalently,(FI) is as follows:
(8)maxρ{Ωp(ρ)-12tp∥ρ-λp∥2}.
The regularized model (FI) has embedded in it the process (decomposed) plans secants and intends to determine a direction of ascent through the accumulated residue, with the approximate calculation of the dual function φ(λ) in (DI), through Benders decomposition. The lemma and the proposition that follow seek to justify the existence and uniqueness of the solution of the quadratic subproblem, like it’s the aggregate subgradient.Lemma 1 (see LemmaXV.3.1.1 in [69]).
The problem (8) has a unique solution ρp+1 characterized by
(9)ρp+1=λp+tpg^p,g^p∈∂Ωp(ρp+1).
Furthermore
(10)Ω(λ)≤zL(λp)+(g^p)t(λ-λp)+e^p,∀λ,
where
(11)e^p=Ω(ρp+1)-zL(λp)-tp∥g^p∥2.Proof.
Suppose nonempty set generated by linear constraints, the existence and uniqueness of the solutionρp+1 following the definition of a positive quadratic. The optimality condition for this solution is
(12)0∈∂Ωp(ρp+1)-1tp(ρp+1+λp).
Then(13)Ω(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)
which is equivalent to
(14)Ω(λ)≤zL(λp)+(g^p)t(λ-λp)-zL(λp)+Ω(ρp+1)+(g^p)t(λp-ρp+1).
Considering (9) recognizes the expression (11) of e^p.Proposition 2 (see LemmaXV.3.1.2 in [69]).
With the notation of Lemma1, consider a quadratic function Ψ:ℝn→ℝ∪{∞} satisfying
(15)Ψ(λ)≤zL(λp)+(g^p)t(λ-λp)+e^p=:φ~(λ),∀λ,
where equality in λ=ρp+1. Then ρp+1 maximizes the function
(16)Ψ~(λ)≔Ψ(λ)+12tp∥λ-λp∥2.Proof.
Applying (9) and (11) and defining relations Ψ can be written as follows:
(17)Ψ(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)-Ω(ρp+1)+(g^p)t(ρp+1-λp)+zL(λp)+e^p,∴Ψ(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)
with equality in λ=ρp+1. Subtracting the term (1/tp)(λ-λp)=0 both sides,
(18)Ψ~(λ)≤Ω(ρp+1)+(g^p)t(λ-ρp+1)-12tp∥λ-λp∥2,
even with equality  λ=ρp+1. Now note that the function of the right side is maximized when
(19)g^p-1tp(λ-λp)=0,
corresponding to ρp+1, given by (9).The functionφ~(λ) is known to aggregate linearization approximation of φ, where the limit on the model Ω, as described in Lemma 1.A more convenient way to solve(FI) is to be made through the dual problem. Define the Lagrangian and their optimality conditions as follows:Ford:=ρ-λp,
(20)ℓ*(w,d,η)=w-12tp∥d∥2-∑r∈{1,…,ℓ)ηr(w-(gr)td-zU(ρr)),η≥0ℓw*=0∴∑r∈{1,…,ℓ)ηr=1,ℓd*=0∴-12tpd+∑r∈{1,…,ℓ)ηrgr=0.
Complementarity,
(21)ηr[w-(gr)td-zU(ρr)]=0,r≥1.
Substituting these equations into ℓ*, it has the following quadratic linear problem:
(DFI)min℘(η),s.t.∑r∈{1,…,ℓ)ηr=1,s.t.ηr≥0,
where
(22)℘(η)=tp2∥∑r∈{1,…,ℓ)ηrgr∥2+∑r∈{1,…,ℓ)ηrzU(ρr).Consider that the optimality conditions have also to update the multiplier(23)ρ=λp+tp(∑r∈{1,…,ℓ)ηrgr),
where η is single solution of (DFI).


## 5. The Approximate Algorithm of Bundle

### 5.1. Algorithm Partial Benders

At each iteration, the multiplierλ is used in subproblem (D), what, resolved, provides an upper bound zU and generates a new Benders cut to be included in the relaxed master problem (MB). Solving this provides a lower limit zL and a variable y for subproblem (L), which in turn is resolved in x. With λ fixed, this process is repeated and accumulated up all the cuts in the master problem Benders (MB), until the test (6) is satisfied. At the end of this process the values ​​of x, y, zU, and zL are taken to the regularized model, a new update to the multiplier.Note. We chose to include the quadratic model only the cut that corresponds to the test (6). However, we can include all cuts, leaving for future work the selection policy and proper disposal.


### 5.2. Approximate Test Armijo

One approach test Armijo [8] here will determine that the direction of the approximation increases φ. Thereby,
(24)δp:=Ω(ρp+1)-zL(ρp)-12tp∥ρp+1-λp∥2,
where ρp+1=λp+tpg^ and  Ω is given by (7).Approaching the values​​of φ by lower quotas (zL(λ)) and upper (zU(ρ)) has
(25)φ(ρp+1)-φ(λp)≤zU(ρp+1)-zL(λp).For0<m1<1 provided, an approximation of the test Armijo will be satisfied in ρp+1 if
(26)zU(ρp+1)-zL(λp)≥m1δp,
where the left side is positive because
(27)zU(ρp+1)-zL(λp)≥zU(ρp+1)-zL(ρp+1)≥0.If we compare this to the test that corresponded to the exact calculation of the functionφ, observed that the difference between the current and the candidate has been replaced by an increase as much as δp is an increase of the exact value. This expects that the test stop approximate Bundle method will not be anticipated, since also ensures a good approximation to the function φ.


### 5.3. Regularization Algorithm for Updating the Multipliers with Relaxation

Before we present the algorithm and in order to keep the notation, replace the model(FI) that is equivalent to
(6′)w(λp)=max(w,ρ)w-12tp∥ρ-λp∥2,s.t.w≤(gr)t(ρ-ρr)+er+zU(λp),r≥1,
where
(28)er≔e(λp,ρr,gr)≔zU(ρr)-zU(λp)+(gr)t(ρr-λp).We used without distinctionsg(ρr)  and  gr.Algorithm 3.
Initialization: They are given tolerance stopδ_≥0 and θ>0. Consider ℓ->0 the maximum size of the Bundle,    t1>0. Get an initial dual feasible solution λ1, y0∈Y and  x0 initial feasible solution (L); that is, for y=y0,   x0 is solution of
(29)Akxk=Kk-Bky1,k=1,…,4,xk∈Xk,k=1,…,4.
Calculate g1=g(λ1). Make zU(λ1):=ℓ(x0,y0,λ1). Estimate zL(λ1), for example, through an iteration of the Benders method. Choice m1∈(0,1) reducing the test Armijo, α∈(0,1) is the reduction in quality test approximation φ. Initialize the set of ascent P=ϕ, the accountant of iterations p=1, and the size of the bundle ℓ=1. For e1=0, corresponding to the initial bundle (g1,e1), and the initial model
(30)ρ⟶Ω1(ρ)≔zU(λ1)+(g1)t(ρ-λ1).Step 1 (principal calculation and test stop).
Whetherρp+1 is the unique solution of the quadratic problem such that
(31)ρp+1=λp+tpg^p,whereg^p∈∂Ωp(ρp+1).
Make(32)e^p≔Ωp(ρp+1)-zL(λp)-tp∥g^p∥2,δp≔Ωp(ρp+1)-zL(λp)-tp2∥g^p∥2.
Calculate through of the algorithm
(33)zU(ρp+1),zL(ρp+1),g(ρp+1).
If δp≤δ and zU(ρp+1)-zL(ρp+1)>θ, stop.Step 2 (approximation test Armijo).
IfzU(ρp+1)-zL(λp)≥m1δp, m1∈(0,1) is “serious step”; otherwise, it is “null step,” check to Step 4.Step 3 (serious step).
Makeλp+1=ρp+1.
Addp the set P; for r=1,…,ℓ.
Permuteer and e^p by, respectively,
(34)er+zU(λp)-zU(λp+1)+(gr)t(λp-λp+1),e^r+zU(λp)-zU(λp+1)+(g^r)t(λp-λp+1).Step 4 (control of bundle size).
Ifℓ=ℓ-, then eliminate at least two of the bundle elements and insert the element (g^p,e^p).
Consider(gt,et)t=1,…,ℓ  the new bundle obtained (withℓ=ℓ-).Step 5.
Insert(gℓ+1,eℓ+1) to the bundle, where eℓ+1=0 in the case of serious step, and in the case of null step,
(35)eℓ+1=zU(ρp+1)-zU(λp)+(gℓ+1)t(ρp+1-λp).
Replace ℓ by ℓ+1, and update the model ρ→Ωp+1(ρ)≔minr{(gr)t(ρ-λp+1)+zU(ρr)}.Step 6.
Makep=p+1, and return to Step 1.


### 5.4. Partial Benders Algorithm for Integer Linear Problem with Relaxation

Initialization: makeq=1.Step 1.
Solve(36)vD=max(vi,ui)∑i=14ditVi+∑i=14(Ki-Biy1)tui,s.t.Ditvi+Aitui≤c~i,wherec~i={ci,i=1,2,ci+Citρp+1,i=3,4.
If there is no solution, stop: (φ1) has no feasible solution. Otherwise, (v(p,q),u(p,q)) solution, and then
(37)zU(ρp+1)=∑j=12eityj+ρtC2y2+vD.
Generate a new constraint (cut) from (ρp+1,v(p,q), and u(p,q)). Continue with Step 2.Step 2.
Solve(38)minz,s.t.z≥∑j=12ejtyj+(ρp+1)tC2y2+∑i=14ditviq+∑i=14(Ki-Biy)t,z∈ℝ,y∈Y,∀q.
Consider(zL(ρp+1),yp+1) the optimal solution. Continue with Step 3.Step 3.
Solve(39)min∑k=14cktxk+(ρp+1)t(C3x3+C4x4).s.t.Akxk=kk-Bky1p+1,k=1,…,4.xk∈XR,k=1,…,4.
Whetherxp+1 solution; continue with Step 4.Step 4 (test quality approachφ).
If(40)zU(ρp+1)-zL(ρp+1)≤α(zU(λp)-zL(λp))
end.
Otherwise, makep+1=p,  q=q+1, and return to Step 1.Remarks
(1)
The test for stopping the algorithm adds to the usual toleranceδ_ of bundles, the requirement that the function approximation is reasonable. In fact, for crude approximations of φ, it is possible to have false serious steps with error δ false small, hence the need for θ-approximation.
(2)
The Benders relaxed master problem(MB) should have some heuristics for selecting cuts, given that the accumulations of all inequalities explode the subproblem.We present Figure1 of the algorithm for the problem with integer linear relaxation.Figure 1


### 5.5. About Convergence

We opted to observe thatθ small enough for the results cited correspond to guarantee the stability of the algorithm of bundle. This can be observed by adding a positive parameter θ→0, the expression of errors linearization, and the gains predicted by the model (see, Lemma  3.2.1 in [69]. Thus if only guarantee the local convergence. Furthermore, the quality test approximation (φ1) should be sufficient for obtaining convergence of the overall strength because the iterative process to arrive at the usual formulation of the bundle, with θ = 0. Undoubtedly, with the risk of being a high cost computational algorithm, as already noted. It presents the known result that guarantees no cycling algorithm Benders.Theorem 4.
The vectors composed of the vertices and their multipliers(vp,up, and λp) generated at each iteration by the algorithm are different.Proof.
Suppose that the first(p≥1) extreme points, say (v1,u1),(v2,u2),…,(vp,up) the problem generated (D)  (λ) and λ1,…,λp obtained problem regularized (FI).
Then with the Step2, it has
(41)minz,s.t.z≥∑j=12ejtyj+(λs)tC2y2+∑i=14bitvip+∑i=14(Ki-Biy1)tuip,s.t.z∈ℝ,y∈Y,s≤p.
The optimal solution of this problem z, y, that is, for some k  (1≤k≤p), s=1,…,p(42)z=∑j=12ejtyj(λk)tC2y2+∑i=14bitvik+∑i=14(Ki-Biy1)tuik≥∑j=12ejtyj+(λs)tC2y2+∑i=14bitvis+∑i=14(Ki-Biy1)tuis.
As z is a lower bound on the optimal cost primal relaxed φ, φ≥z, and with (42),
(43)∑i=14bitvik+∑i=14(Ki-Biy1)tuik≤φ-(∑j=12ejtyj+(λk)tC2y2).
On the other hand, in the next iteration of (D)(λp+1) the solution (vp+1,up+1) is a vertex U(λ). Then
(44)∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1=∑K=14cktxk+(λp+1)t(C3x3+C4x4),
where x is a solution of (L)(λ).
As(x,y) is a viable solution φ it has
(45)∑j=12ejtyj+(λp+1)tC2y2+∑K=14cktxk+(λp+1)t(C3x3+C4x4)≥φ.
Equivalently
(46)φ-∑j=12ejtyj≤∑K=14cktxk+(λp+1)t(C3x3+C4x4)+(λp+1)tC2y2.
Combining (43) and (44), it has
(47)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2≤φ-∑j=12ejtyj≤∑k=14cktxk+(λp+1)t(C3x3+C4x4)+(λp+1)t(C2y2)=∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1+(λp+1)tC2y2.
If φ-(∑k=14cktxk+(λp+1)t(C3x3+C4x4))=∑j=12ejtyj+(λp+1)tC2y2 then (x,y) solves the relaxed integer linear problem (φ).
Otherwise,(48)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2<∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1+(λp+1)tC2y2
in which case (vk,uk,λk)≠(vp+1,up+1,λp+1).
But inequality (42) is as follows:
(49)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2≥∑i=14bitvis+∑i=14(Ki-Biy1)tuis+(λp+1)tC2y2,≥∑i=14bitvis+∑i=14(Ki-BiY1)tuiss=1,…,p.
On the other hand, of (48),
(50)∑i=14bitvis+∑i=14(Ki-Biy1)tuis+(λs)tC2y2<∑i=14bitvip+1+∑i=14(Ki-Biy1)tuiP+1+(λp+1)tC2y2,s=1,…,p,
and therefore (vp+1,up+1,λp+1)≠(vs,us,λs) s=1,…,p.Corollary 5.
Ifq>1, the mth iteration internal, then ym+1≠ym.Proof.
Suppose the contrary, that to solve(MB) with m cuts, the solution y is repeated. In this case, to solve the problem (D), we would obtain a vector (vm+1,um+1) satisfying
(51)∑i=14ditviℓ+∑i=14(Ki-Biy1)tuiℓ=∑i=14ditvim+1+∑i=14(Ki-Biy1)tuim+1
for some  ℓ={1,…,m}. However, this only occurs when the optimality criterion is reached.


## 5.1. Algorithm Partial Benders

At each iteration, the multiplierλ is used in subproblem (D), what, resolved, provides an upper bound zU and generates a new Benders cut to be included in the relaxed master problem (MB). Solving this provides a lower limit zL and a variable y for subproblem (L), which in turn is resolved in x. With λ fixed, this process is repeated and accumulated up all the cuts in the master problem Benders (MB), until the test (6) is satisfied. At the end of this process the values ​​of x, y, zU, and zL are taken to the regularized model, a new update to the multiplier.Note. We chose to include the quadratic model only the cut that corresponds to the test (6). However, we can include all cuts, leaving for future work the selection policy and proper disposal.


## 5.2. Approximate Test Armijo

One approach test Armijo [8] here will determine that the direction of the approximation increases φ. Thereby,
(24)δp:=Ω(ρp+1)-zL(ρp)-12tp∥ρp+1-λp∥2,
where ρp+1=λp+tpg^ and  Ω is given by (7).Approaching the values​​of φ by lower quotas (zL(λ)) and upper (zU(ρ)) has
(25)φ(ρp+1)-φ(λp)≤zU(ρp+1)-zL(λp).For0<m1<1 provided, an approximation of the test Armijo will be satisfied in ρp+1 if
(26)zU(ρp+1)-zL(λp)≥m1δp,
where the left side is positive because
(27)zU(ρp+1)-zL(λp)≥zU(ρp+1)-zL(ρp+1)≥0.If we compare this to the test that corresponded to the exact calculation of the functionφ, observed that the difference between the current and the candidate has been replaced by an increase as much as δp is an increase of the exact value. This expects that the test stop approximate Bundle method will not be anticipated, since also ensures a good approximation to the function φ.


## 5.3. Regularization Algorithm for Updating the Multipliers with Relaxation

Before we present the algorithm and in order to keep the notation, replace the model(FI) that is equivalent to
(6′)w(λp)=max(w,ρ)w-12tp∥ρ-λp∥2,s.t.w≤(gr)t(ρ-ρr)+er+zU(λp),r≥1,
where
(28)er≔e(λp,ρr,gr)≔zU(ρr)-zU(λp)+(gr)t(ρr-λp).We used without distinctionsg(ρr)  and  gr.Algorithm 3.
Initialization: They are given tolerance stopδ_≥0 and θ>0. Consider ℓ->0 the maximum size of the Bundle,    t1>0. Get an initial dual feasible solution λ1, y0∈Y and  x0 initial feasible solution (L); that is, for y=y0,   x0 is solution of
(29)Akxk=Kk-Bky1,k=1,…,4,xk∈Xk,k=1,…,4.
Calculate g1=g(λ1). Make zU(λ1):=ℓ(x0,y0,λ1). Estimate zL(λ1), for example, through an iteration of the Benders method. Choice m1∈(0,1) reducing the test Armijo, α∈(0,1) is the reduction in quality test approximation φ. Initialize the set of ascent P=ϕ, the accountant of iterations p=1, and the size of the bundle ℓ=1. For e1=0, corresponding to the initial bundle (g1,e1), and the initial model
(30)ρ⟶Ω1(ρ)≔zU(λ1)+(g1)t(ρ-λ1).Step 1 (principal calculation and test stop).
Whetherρp+1 is the unique solution of the quadratic problem such that
(31)ρp+1=λp+tpg^p,whereg^p∈∂Ωp(ρp+1).
Make(32)e^p≔Ωp(ρp+1)-zL(λp)-tp∥g^p∥2,δp≔Ωp(ρp+1)-zL(λp)-tp2∥g^p∥2.
Calculate through of the algorithm
(33)zU(ρp+1),zL(ρp+1),g(ρp+1).
If δp≤δ and zU(ρp+1)-zL(ρp+1)>θ, stop.Step 2 (approximation test Armijo).
IfzU(ρp+1)-zL(λp)≥m1δp, m1∈(0,1) is “serious step”; otherwise, it is “null step,” check to Step 4.Step 3 (serious step).
Makeλp+1=ρp+1.
Addp the set P; for r=1,…,ℓ.
Permuteer and e^p by, respectively,
(34)er+zU(λp)-zU(λp+1)+(gr)t(λp-λp+1),e^r+zU(λp)-zU(λp+1)+(g^r)t(λp-λp+1).Step 4 (control of bundle size).
Ifℓ=ℓ-, then eliminate at least two of the bundle elements and insert the element (g^p,e^p).
Consider(gt,et)t=1,…,ℓ  the new bundle obtained (withℓ=ℓ-).Step 5.
Insert(gℓ+1,eℓ+1) to the bundle, where eℓ+1=0 in the case of serious step, and in the case of null step,
(35)eℓ+1=zU(ρp+1)-zU(λp)+(gℓ+1)t(ρp+1-λp).
Replace ℓ by ℓ+1, and update the model ρ→Ωp+1(ρ)≔minr{(gr)t(ρ-λp+1)+zU(ρr)}.Step 6.
Makep=p+1, and return to Step 1.


## 5.4. Partial Benders Algorithm for Integer Linear Problem with Relaxation

Initialization: makeq=1.Step 1.
Solve(36)vD=max(vi,ui)∑i=14ditVi+∑i=14(Ki-Biy1)tui,s.t.Ditvi+Aitui≤c~i,wherec~i={ci,i=1,2,ci+Citρp+1,i=3,4.
If there is no solution, stop: (φ1) has no feasible solution. Otherwise, (v(p,q),u(p,q)) solution, and then
(37)zU(ρp+1)=∑j=12eityj+ρtC2y2+vD.
Generate a new constraint (cut) from (ρp+1,v(p,q), and u(p,q)). Continue with Step 2.Step 2.
Solve(38)minz,s.t.z≥∑j=12ejtyj+(ρp+1)tC2y2+∑i=14ditviq+∑i=14(Ki-Biy)t,z∈ℝ,y∈Y,∀q.
Consider(zL(ρp+1),yp+1) the optimal solution. Continue with Step 3.Step 3.
Solve(39)min∑k=14cktxk+(ρp+1)t(C3x3+C4x4).s.t.Akxk=kk-Bky1p+1,k=1,…,4.xk∈XR,k=1,…,4.
Whetherxp+1 solution; continue with Step 4.Step 4 (test quality approachφ).
If(40)zU(ρp+1)-zL(ρp+1)≤α(zU(λp)-zL(λp))
end.
Otherwise, makep+1=p,  q=q+1, and return to Step 1.Remarks
(1)
The test for stopping the algorithm adds to the usual toleranceδ_ of bundles, the requirement that the function approximation is reasonable. In fact, for crude approximations of φ, it is possible to have false serious steps with error δ false small, hence the need for θ-approximation.
(2)
The Benders relaxed master problem(MB) should have some heuristics for selecting cuts, given that the accumulations of all inequalities explode the subproblem.We present Figure1 of the algorithm for the problem with integer linear relaxation.Figure 1


## 5.5. About Convergence

We opted to observe thatθ small enough for the results cited correspond to guarantee the stability of the algorithm of bundle. This can be observed by adding a positive parameter θ→0, the expression of errors linearization, and the gains predicted by the model (see, Lemma  3.2.1 in [69]. Thus if only guarantee the local convergence. Furthermore, the quality test approximation (φ1) should be sufficient for obtaining convergence of the overall strength because the iterative process to arrive at the usual formulation of the bundle, with θ = 0. Undoubtedly, with the risk of being a high cost computational algorithm, as already noted. It presents the known result that guarantees no cycling algorithm Benders.Theorem 4.
The vectors composed of the vertices and their multipliers(vp,up, and λp) generated at each iteration by the algorithm are different.Proof.
Suppose that the first(p≥1) extreme points, say (v1,u1),(v2,u2),…,(vp,up) the problem generated (D)  (λ) and λ1,…,λp obtained problem regularized (FI).
Then with the Step2, it has
(41)minz,s.t.z≥∑j=12ejtyj+(λs)tC2y2+∑i=14bitvip+∑i=14(Ki-Biy1)tuip,s.t.z∈ℝ,y∈Y,s≤p.
The optimal solution of this problem z, y, that is, for some k  (1≤k≤p), s=1,…,p(42)z=∑j=12ejtyj(λk)tC2y2+∑i=14bitvik+∑i=14(Ki-Biy1)tuik≥∑j=12ejtyj+(λs)tC2y2+∑i=14bitvis+∑i=14(Ki-Biy1)tuis.
As z is a lower bound on the optimal cost primal relaxed φ, φ≥z, and with (42),
(43)∑i=14bitvik+∑i=14(Ki-Biy1)tuik≤φ-(∑j=12ejtyj+(λk)tC2y2).
On the other hand, in the next iteration of (D)(λp+1) the solution (vp+1,up+1) is a vertex U(λ). Then
(44)∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1=∑K=14cktxk+(λp+1)t(C3x3+C4x4),
where x is a solution of (L)(λ).
As(x,y) is a viable solution φ it has
(45)∑j=12ejtyj+(λp+1)tC2y2+∑K=14cktxk+(λp+1)t(C3x3+C4x4)≥φ.
Equivalently
(46)φ-∑j=12ejtyj≤∑K=14cktxk+(λp+1)t(C3x3+C4x4)+(λp+1)tC2y2.
Combining (43) and (44), it has
(47)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2≤φ-∑j=12ejtyj≤∑k=14cktxk+(λp+1)t(C3x3+C4x4)+(λp+1)t(C2y2)=∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1+(λp+1)tC2y2.
If φ-(∑k=14cktxk+(λp+1)t(C3x3+C4x4))=∑j=12ejtyj+(λp+1)tC2y2 then (x,y) solves the relaxed integer linear problem (φ).
Otherwise,(48)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2<∑i=14bitvip+1+∑i=14(Ki-Biy1)tuip+1+(λp+1)tC2y2
in which case (vk,uk,λk)≠(vp+1,up+1,λp+1).
But inequality (42) is as follows:
(49)∑i=14bitvik+∑i=14(Ki-Biy1)tuik+(λk)tC2y2≥∑i=14bitvis+∑i=14(Ki-Biy1)tuis+(λp+1)tC2y2,≥∑i=14bitvis+∑i=14(Ki-BiY1)tuiss=1,…,p.
On the other hand, of (48),
(50)∑i=14bitvis+∑i=14(Ki-Biy1)tuis+(λs)tC2y2<∑i=14bitvip+1+∑i=14(Ki-Biy1)tuiP+1+(λp+1)tC2y2,s=1,…,p,
and therefore (vp+1,up+1,λp+1)≠(vs,us,λs) s=1,…,p.Corollary 5.
Ifq>1, the mth iteration internal, then ym+1≠ym.Proof.
Suppose the contrary, that to solve(MB) with m cuts, the solution y is repeated. In this case, to solve the problem (D), we would obtain a vector (vm+1,um+1) satisfying
(51)∑i=14ditviℓ+∑i=14(Ki-Biy1)tuiℓ=∑i=14ditvim+1+∑i=14(Ki-Biy1)tuim+1
for some  ℓ={1,…,m}. However, this only occurs when the optimality criterion is reached.


## 6. Conclusion and Future Works

Our main goal was to present an alternative technique using Lagrangian relaxation in solving a problem in integer linear programming. The work introduced a new algorithm structured from a block of relaxation of constraints that the problem presents difficulties when approached by traditional techniques Benders. We hope to take advantage of the computational process smoothing over other heuristic algorithms (Dantzig-Wolfe, subgradient) because its search direction is determined by processes similar to bundle method, which has shown proven results superior to those in many large problems [60]. It seems also unlikely that the technique of “Cross Decomposition” would be adaptable. As future works, we investigate other applications in order to verify the efficiency of the methods on structured problems and extend the decomposition to nonlinear problems and integer nonlinear, using the Lagrangian heuristic process along with the regularization. It is expected that other hybrid methodologies [71–74] can be applied in the solution of the problem (P) [1].



---

*Source: 678783-2013-07-16.xml*