qwertyuiopasdfghjklzxcvbnmqw

ertyuiopasdfghjklzxcvbnmqwert
yuiopasdfghjklzxcvbnmqwertyui
opasdfghjklzxcvbnmqwertyuiopa
INTEGER PROGRAMMING

Operations Research I
sdfghjklzxcvbnmqwertyuiopasdf
17/06/2020
ghjklzxcvbnmqwertyuiopasdfghj
Marcela Alejandra Medina Fernández

klzxcvbnmqwertyuiopasdfghjklz
xcvbnmqwertyuiopasdfghjklzxcv
bnmqwertyuiopasdfghjklzxcvbn
mqwertyuiopasdfghjklzxcvbnmq
wertyuiopasdfghjklzxcvbnmqwe
rtyuiopasdfghjklzxcvbnmqwerty
uiopasdfghjklzxcvbnmqwertyuio
pasdfghjklzxcvbnmqwertyuiopas
dfghjklzxcvbnmqwertyuiopasdfg
hjklzxcvbnmqwertyuiopasdfghjk
5.1. Introduction and application cases
Many applications cannot be addressed with the solution methods of Programming.
Linear because they have the principle of "non-divisibility", that is, some or all
variables must take integer values. Models must often be built for
assign people, machines, or vehicles to the activities, in whole quantities. If the
the problem of requiring integer values is the only difference that a problem has with its
formulation in terms of Linear Programming, then it is a problem of
Integer Linear Programming or simply Integer Programming. Thus, the model of
Integer Programming is simply a mathematical model of Linear Programming that
add the condition that some or all of the variables must be integers.

An Integer Programming model is one whose optimal solution makes sense only
if one part or all of the decision variables take values restricted to integer numbers,
allowing to incorporate into the mathematical modeling some aspects that are left out
of the scope of Linear Programming models.

In this sense, the resolution algorithms for Integer Programming models

they differ from those used in Linear Programming models, standing out among them is the
Branch and Bound Algorithm, Branch & Cut, Cutting Planes
Cutters, Lagrangian Relaxation, among others.

Integer problem (IP).

It is a variant of the Linear Program, for which all decision variables in addition to
to meet the non-negativity condition, all must be integers. Consequently, the model

generalized mathematician is:

The solution methods developed for this model are as follows.

1. Cutting plan method.

2. Gomory's fractional algorithm
3. Pure integer Gomory algorithm
4. Bisection and bounding method
5. Land-Doig Algorithm.

Marcela Alejandra Medina Fernández

Integer Programming models can be classified into 2 main areas:
Mixed Integer Programming (MIP) and Pure Integer Programming (PIP).

Programming
Whole

Mixed (PEM) Pura (PEP)

Mixed Integer Programming (MIP)

This category includes those optimization problems that consider variables.

whole or binary decision but not exclusively. In this way a problem of
PEM can be considered a hybrid between different modeling categories.
being a typical case that considers the mixture of integer variables and variables
continuous (these last features of Linear Programming models).

Incorporation of Fixed Costs

2. Localization and Transportation Issues
3. Electricity Generation Problem

Pure Integer Programming (PIP)

In this category, we find those Integer Programming models that consider

exclusively decision variables that take integer or binary values. An example
the following applications are from it:

1. Assignment Problem
2. Roll Cutting Problem
3. Guest Selection for a Wedding

Marcela Alejandra Medina Fernández

 4. Forest Exploitation Planning
5. Knapsack Problem

Note that in the previous problems (PEP) the set of feasible solutions (or
the domain of feasible solutions) is finite. This will generally occur with the problems of
Integer Programming (pure).

5.2. Definition and models of integer programming and

binary.

x ≥ 0

∈ ⊆ { 1, . . . , n }

YesI = {1, … , } →Pure Integer Linear Programming

YesI ≠ {1, … , } →Mixed Integer Linear Programming
If [0,1],{ ∀ }∈ →Binary programming or 0-1.

In general, an Integer Linear Programming problem can arise for various reasons:

Direct: the variables used are quantitative and integer.

Encoded: Integer variables are used to represent compliance or not
of certain conditions (they are usually variables 0 - 1).
Transformed: Integer variables appear to facilitate modeling of
some conditions (implications, disjunctions, etc.)

Example

A car company has three factories, A, B, and C, and two centers of

distribution, D1 and D2. The production capacities of the 3 factories during a year are
1000, 1500, and 1200 vehicles, respectively. The demands at the production centers.
there are 2300 and 1400 vehicles respectively. The cost of transport by train is 10
pesetas per kilometer and vehicle. If the matrix of distances between the factories and the centers
The distribution is given by the following table, how many vehicles should be manufactured in
each factory so that the transport from each of the factories to each of the
Is the distribution center minimum?

D1 D2

Marcela Alejandra Medina Fernández

 A 1000 2690
B 1250 1350
C 1275 850

Model: transportation problem where the goods to be transported are a

undivided property.
3 2

∑ ∑(10d )
=1 =1

Subject to

x11 + x12≤ 1000

21 + x22<= 1500

31 + x32 ≤ 1200

x11 + x21 + x31 ≥2300

x12+ 22+ 32≥ 1400

∈ +, = 1, 2, = 1, 2, 3

Where

= Number of vehicles to be transported from the factory , = 1,2to the center of

distribution , = 1,2.

A freelance computer engineer wants to apply for a computer project among

5 that are up for competition. It only has budget to pay the application fees for 3.
projects. Which 3 projects to choose?

Expected benefit (in thousands of euros) that can be obtained in 3 years with each one
of the projects.
Estimation of the probability that each of the projects will not be granted

Project 1 2 3 4 5
Benefit (miles 90 150 80 100 120
euros)
Probability from0.4 0.7 0.4 0.5 0.6
rejection

Marcela Alejandra Medina Fernández

Problema: qué proyectos debería solicitar para obtener un beneficio mayor y asegurarse de
that the sum of the rejection probabilities does not exceed 1.5

Simple enumerative method for pure binary PLEs.

This algorithm is only valid for integer linear programming problems with all the
binary variables. We are going to develop the algorithm for a specific format of the PLE:
minimum problem with all costs, cj, non-negative (cj ≥ 0,∀j). Obviously the two
Impositions on the problems do not constitute a restriction for the type of problems.
a resolver. If a problem is maximization, it is enough to consider the minimization of its
opposite objective function (max. Z⇐⇒ min−(Z)). On the other hand, if any xj has cj < 0
then the variable change xj = 1 − xj is made, this new variable is also a
binary variable and upon making this change the new variable has its cost equal to cj = -cj >
On the other hand, there is a constant in the objective function that can be suppressed since
it will not affect the optimization process. Therefore, any binary PLE can be used.
at least with all its costs non-negative. Let's see an example

á . = 3x1 +2 2- 5x3− 2x4 +3x5

s.a:

x1 + x2+ 3+ 2x4 + x5 ≤ 4

7x1 + 3 3- 4x^4 +3x5 ≤ 8

11x1 - 6x2+ 3x4 -3x5 ≥ 3

x ∈ {0,1}, = 1, . . . , 5

First, we switch to minimizing by considering the opposite objective function.

= −3x1 -2 2+ 5x3+ 2x4 -3x5

Next, we make the variable changesx1 = 1 - x1, 2= 1 − x2y x5=

1 - x5.
By substituting it, we obtain:

= 3x1 +2 2+ 5x3+ 2x4 + 3x5 - 8

s.a:

-x1 - x2+ 3+ 2x4 - x5 ≤

1 -7x1 +3 3- 4x4 -3x5 ≤ −2

-11x1 + 6x2+ 3x4 +3x5 ≥ 1

Marcela Alejandra Medina Fernández

 x1, x2, 3, x4, x5 ∈ {0, 1

And finally, to apply the algorithm that we are going to develop, we order the variables.
del problema según el coeficiente de la función objetivo, de menor a mayor valor
(forgetting the constant):

= 2 2+ 2x4 +3x1 +3x5 + 5x3

Once the problem is arranged in the indicated form, the idea of the procedure is very
simple. On one hand, we keep in a variable the best value found so far
moment, initially = ∞ (upper bound of the optimal value). On the other hand, we try to
find the solutions in increasing order of the objective function (from best to worst solutions).

The best possible solution, if feasible, would be the solution with all the variables.
taking zero value.

2= x4 = x1 = x5 = x3= [Link] this solution does not verify the second one.
restriction (neither the third), therefore it cannot be a candidate for being an optimal solution.

Now we continue considering solutions where only one variable takes the value 1 and the
the remainder is zero. The variable that takes the value 1 is taken following the order in which it appears in the
objective function, since, for example, if x2 = 1 and the rest zero, it would be a feasible solution
surely it couldn't be improved by x4 = 1 (remainder zero), or x1 = 1 (remainder zero), etc.

2equals 1and the rest of the variables have zero value. Solution that does not satisfy the second.
restriction

We consider the following best solution in which only one variable takes value, which is
x4 = 1and the rest zero.

x4 = 1 (rest zero), infeasible solution due to constraint 1.

1 = 1 (rest zero), infeasible solution due to restriction 3.
x5 = 1 (zero rest), feasible solution with value 3. Since this value is better
(less) than the best stored solution (so far we have none)
stored solution), we save the solution and update the upper bound
= 3.

There is still one solution in which only one variable takes value, x3, but this solution does not
check why x3 is to the right of x5 and its coefficient in the function
the objective will be equal to or worse (greater).

After verifying the solutions in which only one variable takes a value, we move on to
consider the solutions in which two variables take the value 1 and the rest are zero. The
the best of them will be the solution in which the first two variables of the objective function

Marcela Alejandra Medina Fernández

ordered take value, then when the first and the third take value, then when
the first and the fourth take value, and so on.

From the moment a upper limit Z is available, the first thing to do before
checking feasibility is checking the value of the objective function, if that value is
worse than that of the quota, such a solution is not worth it and is eliminated because
we will call annotation. If the value is better, we proceed with the verification of the
feasibility.

2x^4 = 1 (reset zero). The = 4 > Z =3therefore regardless

if that solution were feasible, it could not improve the one we already have.
therefore it is discarded.

that solution was, in terms of the objective function value, the best candidate of all
(it has the two variables on the far left of the ordered objective function). Therefore,
any solution of two variables taking value 1 will be equal to or worse than it and since it already is
worse than the one that defined the upper bound, we automatically discard, by restriction,
all solutions with two variables taking value 1.

Solutions with 3, 4, or 5 variables taking value are automatically discarded because

the best of each of them contains in particular x2 = x4 = 1 which provided a value
worse than the stored upper limit.

Once all the solutions have been studied, implicitly or explicitly, the optimal solution
corresponds to the last time the Z elevation was updated. In our case, the solution is
x5 = 1, x1 = x2= 3x^4 = 0 After obtaining it, we undo the variable changes.
obtaining as a solution 1 = 1 , 2= 1, 3= 0, x4 = 0, x5 = 0with a =
5.

Binary

There is an assembly line, the characteristics of which allow addressing the problem of
balanced as an SALBP problem. It is known that the cycle time is 100
seconds, the standard times for the tasks are in the following table:

Task Tiempo (s) Predecessor

A 40 -
B 75 A
C 50 A
D 35 C
E 80 B,D

Marcela Alejandra Medina Fernández

The following diagram better explains the problem:

The objective in this problem is to minimize the number of machines to be used, starting from
assuming that one machine is needed for each task.

Solution We identify the problem as a SALBP, type 1, since the cycle time is
Given (100 seconds), binary integer programming will be used to find the
minimum number of machines or stations of the line.

The objective function is proposed according to the following criterion.

=∑∑
=1 =1

Where Ci = cost coefficient

Where Ci = cost coefficient

Xik = 1, if task i is assigned to station k; or Xik = 0, otherwise.

The problem constraints are stated as follows: ∑ =1 ≤ for k=1,2,…,k.

Unit allocation restriction: =1 ∑ = 1for i=1,2,...,N.

Unit allocation constraint: ≤ =1 ∑ for b=1,2,…,k and € IP:Restriction of

precedence.

Considering the previous methodology, we proceed to solve the proposed problem:

Initialization

Xik = Task assigned to station k, where i = a, b, c, d, e; Y k = 1, 2, 3, 4, 5.

We set the objective function where we add positional weights of 1, 2, 3, 4, and 5 to

each machine respectively, so that machine or station one has priority
About the 2, 3, 4, and 5, the 2 about the 3, 4, and 5; and so on respectively, such that if it is not necessary the
The workstations are to be occupied by the first stations as a priority.

Marcela Alejandra Medina Fernández

From min=

Now we present the constraints starting with the cycle time constraint:

The following are the unit assignment constraints:

And finally, we outline the precedence constraints, starting with the

corresponding to the restriction that the immediate predecessor of b is a, so a must
be assigned in order to assign b.

The immediate predecessor of c is a, therefore the following applies:

The immediate predecessor of d is c:

Marcela Alejandra Medina Fernández

Finally, e has two immediate predecessors, b and d, with the restrictions posed as follows:

As can be seen, it is a very extensive problem with 30 constraints, for which

solution implements free software called WinQSB, obtaining as
the following result:

5.3. Gomory Method

There are problems that do not accept a real number as a solution, there are many cases.
where this method is used, a case of personnel selection if the result is 1.5, no
we can talk about 1.5 people that is why a method was developed in search of
these solutions.

The Gomory algorithm is a procedure used to find integer solutions.

when the results obtained are in decimals or fractions. This method was created by
Ralph Gomory.

Marcela Alejandra Medina Fernández

Gomory fue el primer creador del algoritmo para resolver métodos de programación entera,
the Gomory algorithm consists of solving the problem without considering the constraints of the
integer character of the variables and if the solution is not integer add constraints that reduce
the set of solutions of the associated continuous linear problem, not excluding any
integer solution in mathematics.

Example

Max Z = 7x1 + 10x2

Subject to:

-x1 +3 2≤ 6

7x1 + x2≤ 35

x1, 2less than or equal to 0

Transferring the equations to the table:

Ending the simplex method:

Marcela Alejandra Medina Fernández

The simplex method terminates because it has all positive values.

Choosing the smallest from the last table:

7
2=
2
2/7 is chosen and the restrictions from the table are taken.

The constraint should be broken down into integers and positive fractions less than 1.

The integers are arranged on the left side and the fractions on the right side.

Marcela Alejandra Medina Fernández

We add<= 0to the restriction and the integers are removed

We move the values without variable to the right side and add a slack variable.

The constraint is added in a new row to the last simplex table.

To obtain the pivot column, it is divided

s3

The smallest positive one is chosen, taking into account that the results are absolute.

Marcela Alejandra Medina Fernández

S3 will be the pivot row for having a negative result in the solution - (1/2).

The simplex method is repeated.

5.4. Bifurcation and Bounding Method

The branch and bound method (B&B) solves an LPPL
solving an ordered sequence of PPLs that are obtained by relaxing the restrictions of
integrality and adding additional constraints. The number of additional constraints
grows as the B&B method progresses. These restrictions allow for separating the region
feasible in complementary subregions.

The B&B method initially establishes lower and upper bounds of the optimal value of the
objective function. The bifurcation mechanism progressively increases the value of the bound.
inferior and it also progressively decreases the value of the upper limit. The difference
between these bounds is a measure of the proximity of the current solution to the optimal one, if it is
exists.

By minimizing, a lower bound of the optimal solution is obtained by relaxing the constraints.
of the integrality of the initial PPLE and solving the resulting PPL. In addition, the value of the
The objective function for any solution of the original PPLE is an upper bound of the
optimal solution. Similarly, when maximizing, the solution of the relaxed LP is a

Marcela Alejandra Medina Fernández

the upper bound for the optimum and any solution of the original PPLE is a lower bound of
the optimal solution.
The following are the steps of the B&B algorithm for a Mixed Integer Linear Programming problem:

Step 1: Initiation

1.1 An upper limit is established ( ) and a lower bound (− of the solution

optimal.

1.2 The initial mixed PPLE is solved by relaxing the integrality constraints.

1.2.a If the relaxed problem is infeasible, the original one is as well and there is no
solution.

1.2.b If the obtained solution satisfies the integrality conditions, it is

optimal.

1.2.c In any other case, the value of the corresponding limit is updated.
with the value of the resulting objective function.

Step 2: Fork

2.1 Using the variable xk, which must be an integer and is not, it is generated by
branching two problems. If the value of the variable that is to be an integer xk is a.b,
where a and b are its integer and fractional parts respectively, the problems result
from the bifurcation are the following.

The first problem is the relaxed PPLE to which the constraint is added.
xk ≤ a

2.1.b The second is the relaxed PPLE to which the restriction xk≥a+1 is added.

2.2 These problems are placed orderly in a list of problems to be processed

that are solved sequentially or in parallel. Note that the technique of
The proposed bifurcation completely covers the solution space.

Step 3: Solution

3.1 The following problem is resolved in the list of problems to be processed.

Step 4: Annotation

4.1 If the solution to the current problem satisfies the integrality conditions and the
the optimal value of its objective function is less than the current upper bound, said bound
is updated to the optimal value of the objective function of the solved problem, and the

Marcela Alejandra Medina Fernández

 current minimizer is stored as the best candidate for minimizer of
original problem. In case of maximizations, the current lower bound is updated to
optimal value of the objective function of the solved problem if it is less than this
lower limit.

4.2 If, on the contrary, the obtained solution does not satisfy the restrictions of
integrality and the value of the corresponding objective function is between the bounds
Lower and upper, the value of the lower bound is updated to the value of the function.
objective of the solved problem and it proceeds to bifurcate again. In case of
maximizations, the upper bound value is updated to the value of the function
Objective of the solved problem and proceed to bifurcate again.

4.3 The problems generated in the bifurcation process are added to the list of
problems that need to be solved.

Step 5: Pruning

5.1 Stepwise pruning: It occurs if the solution does not meet the conditions of
integrity and furthermore the value of the objective function of the solved problem is greater
that the upper bound for minimizations is less than or equal to the lower bound for
maximizations. In this case, it is not possible to obtain solutions through
additional bifurcations of that branch.

5.2 Pruning for infeasibility: It occurs if the problem is infeasible.

5.3 Integral padding: It occurs if the solution to the current problem meets the
integrality constraints.

Step 6: Optimality

6.1 If the list of issues to be processed is not empty, proceed to step 3.

6.2 If the list of problems to be processed is empty, the procedure ends.

6.3 Once the problem is completed, if there is a candidate for minimization, that candidate is
the minimizer; otherwise, the problem is infeasible.

The B&B algorithm returns the optimal solution or notifies infeasibility.

step 1 or in step 6. The branching process concludes with the pruning of the branch
corresponding as a consequence of one of the following three reasons:

The solution to the relaxed problem is greater than the available upper bound.
case of minimizations, or less than the available lower bound for the case of
maximizations.
The problem considered is infeasible.

Marcela Alejandra Medina Fernández

 3. The obtained solution meets the integer conditions.

As can be seen, the central steps of the B&B algorithm are branching, bounding, and
pruning. The difference between one B&B algorithm and another lies in the different strategies.
that can be carried out when implementing such steps.

Branching and processing strategies

Any variable that should be an integer but is not in the current solution is a
candidate variable for bifurcation. Which to choose is not a trivial matter, and its answer
It must be based on the structure of the problem.

The problems stored for processing can be addressed through strategies in

depth, width, or mixed. The following figure illustrates the first two alternatives.
Typically, the technical knowledge of the problem allows for the establishment of the type of strategy.
to use

A deep processing strategy quickly leads to problems.

strongly restricted that produce good upper and lower limits. From this
creates insurmountable problems and, therefore, a desirable elimination of
branches.
On the contrary, a broad strategy allows us to address very similar problems,
from which computational advantages can arise such as reoptimization
efficient of the current relaxed problem based on the solution of the previous one.

Boundary strategies

The constraint is usually carried out through what is known as linear relaxation.
consisting of obtaining the limit from the resolution of the PPL obtained by relaxing
the integrality restrictions of the original PPLE.

However, there are other possible relaxations of the original PPLE, such as the relaxation
Lagrangian in which the entire set of constraints (Ax ≤ b in matrix notation) is
eliminated and the objective function of the problem to maximize z=cTx is replaced by
Maximize zR = cTx - (Ax–b), where >=0 is a fixed vector.

If x* is an optimal solution to the original problem z ≤ zR, then by solving the

Lagrangian relaxation the optimal value of zR provides a valid bound for the problem

Marcela Alejandra Medina Fernández

Properly choosing the value of the vector this quota tends to be similar to the
provided by the linear relaxation solution, but with the advantage that without the
restrictions of the problem the resolution of the Lagrangian relaxation can become
much faster.

In contrast, the pruning carried out after the delineation through relaxation.
Lagrangian is not usually as powerful as that carried out after linear relaxation. In
In general, there are two desirable factors when choosing one strategy over another.
(a) a quick resolution of the relaxed problem; and (b) obtaining a good
Quota. In general, linear relaxation tends to offer a good compromise between both.
factors.

Pruning strategies

As mentioned earlier, the pruning of the corresponding branch takes place by

one of the following three reasons:

The solution to the relaxed problem is greater than the available upper bound in the
case of minimizations, or less than the lower bound available for the case of
maximizations.
2. The considered problem is infeasible.
3. The obtained solution satisfies the integrality conditions.

Regarding point 1, one can choose to convert the problem to standard form.
maximization (as seen in Topic 4) and prune whenever the solution of
relaxed problem is less than the current optimal.

Regarding point 3, if the relaxed problem and the subproblem generated by

bifurcation only differ in the absence of some restriction, pruning can simply
based on checking if the optimal solution of that relaxation is a feasible solution for
the subproblem, since in this case this solution will also be optimal for it
subproblem.

Marcela Alejandra Medina Fernández

Marcela Alejandra Medina Fernández
Marcela Alejandra Medina Fernández
5.5. Egon Balas Method and Cutting Planes
The method consists of the following steps (k may vary depending on the
branching)

1. The maximum value of Z (upper bound) Zupper=∞ k=0. Check the feasibility of the
solution (0,0,…0), if it is not feasible to continue with the method, if it is feasible then
the optimal solution has been reached.

2. Branching: The solution subsets are defined:

· (x1, x2, … xk) as a partial solution

Marcela Alejandra Medina Fernández

· (x1, x2, … xk, xk+1, … xn) the second part of the solution is the complement of the
partial solution.

Select from the partial solution (x1, …xk) to make a partition and create two.
new partial solutions one xk+1=1 and another with xk+1=0 and k=k+1

3. Survey: If any of the restrictions are met:

Then there is no feasible solution and the branching stops.

4. The solution is complemented by setting xk+1=1-xk and the rest of the variables equal to
zero. Z is calculated and if Zcota≠∞ and Z> Zcota → it no longer branches.
5. If the solution is feasible and Z < Zcota → Zcota = Z and analysis stops. If the solution
It is feasible then it no longer branches. Return to step 2.

This method is an enumeration procedure that finds the optimum in a more

quick; in the Bullet method, effectiveness consists of evaluating only a few solutions.
The method starts by setting all variables to zero and then through a
a systematic procedure consecutively assigns to one by one of the variables the
value 1. Then it is substituted in each of the constraints and infeasibility is checked.
For this reason, the method is sometimes called the additive algorithm.

To describe the algorithm, the following general form of a problem is considered

Linear Programming with zero–one variables:

Step 1. The objective function must be of the minimization type, with all coefficients not
negatives.

Step 2. All constraints must be of the type £, with the right-hand sides being negative.
necessary. Then, these restrictions are converted into equations, using the variables
auxiliaries on the left side of the constraints. Example:

= 3Y1 +2 2- 5 3– 2Y4 +3Y5

Subject to:

= – 3Y1 - 2 2+ 5 3+ 2Y4–3Y5

Marcela Alejandra Medina Fernández

With its restrictions:

We replace:

Y1 = 1– X1;

2= 1– 2;

3= 3;

Y4 = X4;

5 = 1 – X5

´ = 3X1 + 2 2+ 5 3+ 2X4 +3X5 – 8

Subject to:

We replaceW' + 8 = W

= 3X1 + 2 2+ 5 3+ 2X4 +3X5

With its restrictions:

The always new problem to solve consists of minimizing the objective function,
taking into account the measure of the infeasibility of the slack. When the infeasibility gives
the lowest value, we continue with the next step; in the case of zero infeasibility,
this corresponds to the optimal solution; if we find several infeasibilities equal to zero,
We replace in the objective function and the answer will be the one that makes this function minimum.

Marcela Alejandra Medina Fernández

 1= 0

2= 0

3= 0

X4 = 0

X5 = 0

0 1; 0 -2; 0 – 1Unfeasibility 3

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 2; 0 5; 0–12; Infactibilidad 12

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

["0 2","0 -2","0 5","Infeasibility 2"]

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 0; 0-5; 0-1; Unfeasibility 6

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0–1; 0 2; 0 2; Unfeasibility 1

X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

Marcela Alejandra Medina Fernández

0 2; 0 1; 0 2; Infeasibility 0

Unique Optimal Solution:

X * 10

∗ 2= 0

∗ 3= 0

X * 4= 0

X * 5= 1

∗=3

Unique Optimal Solution for the original problem:

Y * 1= 1

∗2= 1

∗ 3= 0

Y * 4= 0

Y * 5= 0

∗=5

Some authors use the modified Balas algorithm, which consists of introducing it
the model a constraint called filter, which is nothing other than the objective function
with a lower bound of the optimal value. Historically, it is very important, as it has
it has been shown that effective integer programming algorithms could be used
the implicit enumeration.

Shear Plane Method

The fundamental idea behind the cutting plane algorithm is to start with a solution
initial feasible solution for the relaxed problem, to then 'cut' or remove that solution and

Marcela Alejandra Medina Fernández

change it for another that improves the value of the objective function being optimized (it is
to say the value of the Lagrangian Dual Problem.

In addition, to start this method, it is necessary to have a special consideration:

The set of points that constitute the feasible integer solutions of the problem
relaxed must be limited.

Why?: Because the cutting plane algorithm uses these points, so if

the set was unbounded, then the algorithm would never converge (that is, never
it would finish iterating). This bounded set is known as the convex hull, but
caution: it is not just any, it is the convex hull of the integer solutions of the problem
relaxed.

Shear Plane Method (Dual Optimization)

by GEO Tutorials on 31/08/2016 in Whole Programming 2

In a previous tutorial, we discussed Lagrangian Relaxation, and thanks to that

For example, we saw that by varying the values of the variables associated with relaxation (more
known as the Lagrange Multipliers), the value of the objective function of
The Dual Lagrangian Problem is approaching the value obtained by solving the
original problem. In simple words, what was done in that example was to optimize the
multipliers.

Marcela Alejandra Medina Fernández

In this article, what we will see is a different way to optimize these variables.
through an algorithm known as the Shear Plane Method or Method of
Cutting Plans (or simply Cutting Plans). This algorithm is also known as
name of cuts based on Benders decomposition, and this is mainly due
to that this procedure uses inequalities very similar to those used in the
method proposed by J.F. Benders.

The fundamental idea behind the cutting plane algorithm is to start with a solution
initial feasible solution for the relaxed problem, to later 'cut' or remove that solution and
change it for another that improves the value of the objective function being optimized (it is
say the value of the Lagrangean Dual Problem.

Additionally, to start this method it is necessary to have a special consideration:

The set of points that constitute the feasible integer solutions of the relaxed problem.
It must be limited.

Why?: Because the cutting plane algorithm uses these points, so if

the set being unbounded, then the algorithm would never converge (that is, never
it would finish iterating). This bounded set is known as the convex hull, but
caution: it is not just any, it is the convex hull of the integer solutions of the problem
relaxed.

convex hull continuous relaxation

Let's see how this method works in general. Let's assume we have
the following problem, where the second set of constraints Cx ≤ d is "difficult" and

Marcela Alejandra Medina Fernández

it complicates the resolution, therefore we take it out and bring it to the objective function, to the
what we will call the relaxed problem:

Furthermore, let us assume that it is possible to enumerate all the points that are feasible for
our relaxed problem (that is, those that are within the convex hull). If
we could do that, then it would be enough to evaluate all those in the objective function
points, and see which one delivers the lowest value: this point would then be our solution.
optimal.

What is mentioned above can be mathematically represented as follows

form, where p is the number of points that belong to the integer solutions of this
relaxed problem:

With the above in mind, we can then express our Dual Problem.
Lagrangian in the following form:

Which can be reformulated and expressed as an optimization problem.

This reformulation is known as the Master Problem, where we use a variable.
auxiliary u and is expressed in the following way:

This reformulation is important to understand, as it is thanks to having each one

of the points that belong to the integer solutions of the relaxed problem (remember that
we said that they could be enumerated), then each of the restrictions of the type:

Marcela Alejandra Medina Fernández

They constitute a cut for our problem.

This leads us to the following question: if we have all the points, then we add
all the cuts immediately (simultaneously)?

The answer is NO, as this would be a very tedious job and would take a lot of time.
computational. For this, there is the cutting planes algorithm, to start adding
iteratively the cuts, in such a way that it takes less time than adding them all at once
set.

As we have called the previous reformulation the Master Problem, then

we need a sub-problem, or slave problem. This sub-problem corresponds to
relaxed problem we discussed at the beginning of the development:

Finally, the last question we can ask ourselves is how many cuts to make. For the
The previous question does not have an answer that we could give a priori as exact, but a
a good approach is that the number of initial cuts (or initial points to be used) is
equal to the number of variables or penalties, increased by one unit, that is:

Número de Cortes Iniciales = Número de Penalizadores + 1

Cutting Plane Algorithm

The cutting plane algorithm can be stated through the following steps. In addition,
then you will find a summary through a flowchart:

1. Sea k=1. Let x1, x2, x3, ..., xr be the number of points needed to start the
Algorithm. Create the cuts of the type bc c4 c^{T}x_{i}+ bb ^{T}(Cx_{i}-d)
with these points.
2. Solve the Master Problem.
3. The master problem will provide an update for the values of the
Lagrange multipliers. With them, solve the sub-problem.
4. By solving the sub-problem, a new point belonging to the
feasible solutions of the relaxed problem. Check the stopping criterion. If
fulfill, finish; otherwise, create a new cut.
5. Add the cut to the Master Problem, make k=k+1 and return to 2.

Marcela Alejandra Medina Fernández

The theory of this procedure can be a bit complicated, so let's take a look at an example.

Example

Let's assume the following optimization problem, where the first four
inequalities will be those that remain in the relaxed problem, and the last 4 are the
"complicated" inequalities that will be incorporated into the objective function.

However, before that, we will present a graphical representation of the problem.

proposed. The shaded area in green corresponds to the domain of feasible solutions
from the continuous relaxation of the problem, that is, omitting the integrality conditions
for the decision variables.

Marcela Alejandra Medina Fernández

In this context, the optimal solution of the continuous relaxation is vertex B where x=30/11
y=42/11, with optimal value V(PL)=186/11=16.909 (approx).

In a similar manner, the optimal solution to the integer problem is identified with the
letter F with x=3 and y=3, with the optimal value V(PE)=15.

Next, we resume the procedure of the Shear Plane Algorithm. For this purpose
we will write the relaxed problem (not to be confused with continuous relaxation!) of the following
form:

Marcela Alejandra Medina Fernández

when writing this problem, the points belonging to the convex hull of the solutions
the solutions of the relaxed problem are the following:

A graphical representation of the convex hull of the relaxed problem is shown at

continuation:

Marcela Alejandra Medina Fernández

Although the method suggests an initial number of cuts, as can be seen in
these examples are only 8 points (denoted by E, F, G, H, I, J plus the coordinates (2,3) and
(3,2)), so we will not follow this suggestion. To begin, we set k=1 and we will use
the point (1,4) to create the following cut:

So the Master Problem in iteration k=1 is:

When solving this problem, the optimal solution is: .

With these values for the Lagrange Multipliers, we solve the relaxed problem:

Marcela Alejandra Medina Fernández

Which results in the values x=5 and y=1, with a target value of 58.5.

Then we check the stopping criterion (0≠58.5) so the new point that allows us
generate a new cut:

We do k=2 and the new Master Problem is:

Which results in the values x=2 and y=4, with a target value of 15.882.

We checked the stopping criterion (13.76≠15.882) so the new point that allows us
generate a new cut:

We make k=3 and the new Master Problem is:

In solving this problem, the optimal solution is:

Marcela Alejandra Medina Fernández

With these values for the Lagrange Multipliers, we solve the relaxed problem:

Which results in the values x=5 and y=1, with a target value of 15.6,
we checked the stopping criterion (15.6=15.6), so since the criterion is met
stop and the algorithm stops.

While optimizing the values for a Lagrangian Relaxation, we have found a

value that meets the following:

Particularly for this problem, it holds that:

Bibliography
[Link]
vos/[Link]

[Link]

[Link]

[Link]

[Link]
operational/files/[Link]

[Link]

[Link]
dual-optimization/

Marcela Alejandra Medina Fernández