{'fraction_non_alphanumeric': 0.031655225019069415, 'fraction_numerical': 0.009398496240601503, 'mean_word_length': 3.9115600749264114, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improving the LP bound of a MILP by branching concurrently

We'll measure the differences of the dual variables and the gain of the objective function when creating new problems, which each has one inequality more than the starting LP-instance. These differences of the dual variables are naturally connected to the branches. Then we'll choose those differences of dual variables, so that for all combinations of choices at the connected branches, all dual inequalities will hold for sure. By adding the gain of each chosen branching, we get a total gain, which gives a better limit of the original problem. By this technique it is also possible to create cuts.


Motivation of the following thoughts
Nowadays the technique for doing MILP (Mixed Integer Linear Programming) is based on the branch and bound method. This method uses the best solution of the linear inequality system with objective function (= LP-instance) by leaving out the integer conditions from the mixed integer linear inequality system with objective function (= MILP-instance). Then this method searches for an 0-1 (or integer) variable x n , which has a non-integer value q n . The next step is to create two new LP-instances by adding first x n = 0 (or x n ≤ [q n ]) and secondly x n = 1 (x n ≥ [q n + 1]). By continuing this process a binary tree of problems is created. Now take two different nodes in this tree, so you look at two different LPinstances. With both problems it is possible that some x n is still not integer. We'll create a branch on that variable for both problems. It can happen at a big and sparse MILP-instance, that the same similar branching will lead to exactly the same calculations at the new LP-instances. From a numerical point of view this is unsatisfactory.
New ideas have been developed here which use some kind of independence of branching. These will help to prevent such double calculations. One further aim of these new techniques is a better measurement and control of what happens at a branching. A practical and short-term outcome should be better limits for huge MILP-instances. It should be noticed that the prominent group of huge Traveling Salesman Problems is a part of this group. As a matter of fact, this group was indeed the starting point of the author's thoughts about this topic.
We'll show that the combination of branches can be described by an ordinary linear inequality system, so that the problem to get an optimal combination of branches will be a LP-instance (luckily not a MILP-instance). We'll reach this formulation at the middle of the second section at theorem 2.7. We want to use instead of a binary tree of depth n, which has 2 n problems, just 2n problems. We'll try to combine the solutions of the 2n problems as well as possible to get a bound for the original problem (MILP-instance), which will be better than the LP-bound but normally not as good as the bound by solving all 2 n problems.
We'll furthermore see that it is even possible to define a very huge LP for each MILP, which represents the ability to combine the several case differentiations.
The main idea is not too difficult: We'll measure the differences of the dual variables and the gain of the objective function when creating new problems, which each has one inequality more than the starting LP-instance. These differences of the dual variables are naturally connected to the branches. Then we'll choose those differences of dual variables, so that for all combinations of choices at the connected branches, all dual inequalities will hold for sure. By adding the gain of each chosen branching, we get a total gain, which gives a better limit of the original problem.
It should be noted that the whole paper has been fully elaborated by the author. In fact the only real reference are the basic facts about LPs as presented in [1].
2 Description of the technique in a very broad context

Basic terminology and central theorem
In the following we examine a problem P , which can be partially represented as a minimal linear problem P l . The desription of the whole problem needs some additional case differentiations. It should be remarked that the set of MILPinstances is a real subset of this problem class. The linear problem P l has a set {y m } of inequalities in variables {x n }. Without loss of the generality we assume that all {y m } are ≥-inequalities. We'll argue later why equations may be excluded from the scope. Furthermore we expect that the inequalities named by y m represent all bounds to the x n . Since the term branching has been used in LP-terminology in quite a lot of places with an emphasize of really creating of one problem two problems, a new terminology will be introduced. We use the terms of cases and files instead. A case C i,j will stand for the evaluation of one possibility j of a case differentiation i, the sum of the cases C i,j make together a file F i , which will be in other words the case differentiation. But we'll soon define it more concretely. We shall examine, when and how the files can be combined to get a higher lower limit for the optimal solution.
Therefore we'll start from the dual point of view, so ω will be considered as the objective function of the dual problem. To ease the notification, we state that the indices {m} and {n} have empty intersection. Via defining the index {r} as the union of both we get something that will help us in making all formulation much easier.
The dual solution space of P l will be noted as V 0 with optimal subspace L 0 and optimal value ω 0 . Furthermore we chose an arbitrary y ∈ L 0 . By looking at one case j of the case differentiation i the dual solution space is V i,j . But we'll restrict this solution space by {ω i,j ≥ ω 0 } to get a polytope P i,j . Now let the case C i,j be the following set {c i,j | y + c i,j ∈ P i,j }. So it is a movement to 0 of P i,j . Our objective function ω i,j can easily expanded to C i,j just by setting it to ω i,j (c i,j ), which is the same as ω i,j (y + c i,j ) − ω i,j (y) due to the linearness of ω i,j .
Definition 2.1 Now choose c i,j ∈ C i,j and define ∆ m i,j (c i,j ) = y m −(y+c i,j ) m = −(c i,j ) m as the change of the m-th dual variable. Also define ∆ n i,j (c i,j ) = r n (y)− r x (y + c i,j ), where r n shall be the reduced cost of x n . By this we also define ∆ r i,j .
It is important to state that the ∆ n i,j (c i,j ) can be calculated by the ∆ m i,j (c i,j ) with additional info of the value of the new dual variable(s) y + c i,j . If we have equalities as conditions, we'll see that those dual values give no interesting ∆ mvalues, but the ∆ n -values can be calculated with the help of these values. We also define the vector l = (y, r n (y)), this vector has coordinates in r. As y + c i,j is a dual solution, all coordinates y m most be positive or null. The same holds for the linear function r n , the value R xn (y + c i,j ) must be positive or null. Putting these facts together, we get the following remark, which already has the structure of our main statement 2.6: For later purpose we also investigate the property of linearity of the ∆ m i,j (c i,j ) and the ∆ n i,j (c i,j ) and so of the ∆ r i,j (c i,j ). We easily see that everything is linear: In 2.2 we call those inequalities, where the right hand side is greater 0 the main inequalities.
Remark 2.4 If c i,j relates to an optimal solution of P i,j , then one main inequality is sharp.
Too see this we assume that this is not the case. We consider y + (1 + ǫ)c i,j , which has higher objective value and the inequalities in 2.2 still hold. As those inequalities make the dual variable related to the inequalities of P i,j positive and the dual inequalities of P i,j true. We follow that (1 + ǫ)c i,j is in C i,j . This is a contradiction to the optimality of c i,j . So one of the main inequalities must be sharp. The other non-main inequalities are in fact trivial, since the values here for y itself are already sharp, so the ∆-values must be negative or null.
The next step of our thoughts is to go from a case to the case differentiations, which will be named as files as announced. Let F i = j C i,j be a file. If we take an element f i = ⊕ j c i,j out of our construct F i . We further define: The delta represent the highest differences of the changes within a case differentiation (file) of the dual variables and the dual inequalities. Based on 2.3 you get easily the following equalities and inequalities.
So you can conclude that the deltas are still convex and ω i is concave. Now we even build a more complex space P, which will be the sum of all files and our final object. This space represents parallel files.
with the following functions for p ∈ P: Now let p ∈ P, then we have chosen in all cases of all files a solution vector. Remember, that we are always talking about dual solutions and variables. If we chose for each file F i a case C i,j(i) , then we have a new problemP l , which is in fact P l together with the inequalities from all C i,j(i) . For this we can calculate a solutionŷ by the means of the ∆: If we look atŷ m , then the value is: So by ∆ m P (p) ≤ y m , we can make sure, that the dual variableŷ m is positive. Since this is not important for equations, we only considered inequalities before. Notice also that the condition is independent of our choice j(i).
For the validity of the n-th dual inequality we got something similar: Keep in mind, that also r n (ŷ) can be calculated by the ∆ m i,j(i) (c i,j(i) ) with the help of new dual variables of all chosen cases. This is the same as the ∆ n i,j (c i,j ) could be derived from the ∆ m i,j (c i,j ), as we have seen before.
The objective value ofŷ is ω 0 + i ω i (c i,j(i) ) ≥ ω P (p). Putting these thoughts together we get our central statement.
Theorem 2.6 (Central theorem) If for all r holds, that ∆ r P (p) ≤ l r , then the original problem P must have an optimal solution that is greater than ω P (p), which is greater than the original ω 0 of the linear problem P l .

Building the little combining LP
The last statement seems to be rather abstract, but by an easy trick, we'll get two different forms, that can be used in an algorithm. To get the first we just substitute f i by λ i f i with λ i ≥ 0. As the deltas and the objectives ω i are linear on a scalar (2.5), we get the main result of this article: Theorem 2.7 (Central theorem -simple form) The ability to combine case differentiations can be assured by the following inequalities: The new lower limit is i λ i ω i (f i ) + ω 0 . So by solving this LP-instance in λ i we get better lower limit for our problem P .
By looking at all P i,j all values in this LP-instance can be calculated, first the (y + c i,j ) m and R xn (y + c i,j ), secondly ∆ m i,j (c i,j ), ∆ n i,j (c i,j ), ω(c i,j ) and lastly the ∆ m i (f i ), ∆ n i (f i ) and the ω i (f i ).
By the definition of ω i it is natural to choose the c i,j in such a way that for all j the equation holds. This can be achieved by substitution of This is for our purposes well-defined, because when ω(c i,j ) = 0 then we get no progress on the objective function of P from this case differentiation. By this substitution in 2.7, the objective function ω i (f i ) remains the same, but normally the ∆-values will decrease, leading to higher values when using the practical form of the central theorem. We call this trick normalization.
As a next step we want to generalize 2.7. We substitute in 2.6 f i by λ i,k f i,k and use the convexness of ∆ r i (2.5) to get the second sum in the upcoming theorem 2.8. Suppose furthermore that you have not only got one optimal solution of P LP , but another solutions y + c 0 ∈ L 0 . This other solution can be found in a case C 0 = F 0 , which by itself already will be a file F 0 . We have furthermore a natural function ∆ r defined as above on this case. In the argumentation to 2.6 we could have introduced this special case without any problems. By this we get an extra term of −c 0 in the calculation ofŷ m . Since y + c 0 is an optimal solution of P l , there will be no quality growth directly related to c 0 . So we don't have to define a function ω for it. Theorem 2.8 (Central theorem -more complex form) The ability to combine case differentiations can be assured by the following inequalities: So by solving this LP-instance S in λ i,k and λ 0,k we get a better lower limit for our problem P .
Although this formulation seems to be much stronger than the version 1, this is not really the case. Looking at the second sum we see, that the λ i,k can be created in 2.7 by choosing F i1,j = F i2,j for i 1 = i 2 . This is possible because it was never stated that we made a case differentiation only once. But by the creation of 2.8 we see something different: If some λ i,k1 and λ i,k2 with k 1 = k 2 are non-null for an optimal solution of the resulting LP-instance in 2.8, then we can find better values by setting . So by generating new columns we can sometimes improve the bound for P . Also the first sum in 2.8 has some limitations. Suppose the following values: Then the files for i 1 and i 2 cannot be combined fully. But if you exchange y and y + c k 0 , they can, because then ∆ m i1 (f i1 ) = ∆ m i2 (f i2 ) = 0 holds. So we should not expect that the first sum in 2.8 to help us very much for our needs.
We have presented in this section a theory on a problem, which is described by a LP too weak. But in truth we studied the dual LP, where the problem is described too sharp and can be weakened by case differentiations. As 2.7 can be weakened by natural case differentiation by fixing for one i and one j ∆ r i = ∆ r i,j , we could use the whole theory on it. This self-appliance is surprising and fascinating. We will sketch one manual example later. Even if this looks interesting on the first glance, not much progress on the lower bound is expected by this iteration.
Although the mathematical formulation to combine case differentiations (files) has been explained broadly in this section, some details are still not covered. The problem is that those details might be not too easy to attack at all. When you think of a fast implementation of this idea you want to have an effective, numerical stable and fast algorithm to find good elements c i,j ∈ C i,j , where most c i,j are zero. By these you get good f i for a given solution y. We'll see later in 3 that the normal approach to use optimal solution of the P i,j leads in some examples to problems. So later in 5.2 and 5.3 we will attack these problems by using non-optimal y + c i,j even before normalization, where most ∆ m i,j (c i,j ) and ∆ n i,j (c i,j ) should be zero.

Building the huge combining LP
In this section we will follow again the made definitions and results and reach a mathematical satisfactory formulation of the theory. We had started with one solution y ∈ V 0 . For each case of a file we have also a y i,j ∈ V i,j . Notice that the reduced costs of one variable of y 0 (and y i,j ) are by definition just a linear equation dependent of the (y 0 ) n ((y i,j ) n ). So we define as in 2.1 the ∆ r i,j as variables which are calculated by linear equations from y 0 and y i,j , the same holds for the ω i,j , which are also linear dependant on y 0 and y i,j . Via the restrictions ∆ r i ≥ ∆ r i,j and ω i ≤ ω i,j for all j we have defined ∆ r i and ω i as linear inequalities. Like before we define ∆ r P as a sum of the ∆ r i and ω P as the sum of the ω i plus the objective ω of P l , which is also a linear term of y 0 . Via using the restrictions of 2.6 and setting the objective to ω P we have defined now a very huge LP P comb . We can now easily formulate a theorem, which describes the problem of doing case differentiations in parallel in a mathematical satisfactory way: Theorem 2.9 (Central theorem -complete form) Each solution of P comb represents a lower bound of P .
The optimal value is the optimal lower bound possible via our combining technique. We restricted ourselves from writing all inequalities explicitely down, as the huge amount of indices for each variable might only be confusing and all inequalities have already been described impliciteley.
But it should be noticed that the definitions in 2.7, 2.8 and 6.1 are just tightened and less complex inequalities systems than this system. Consider that P has n variables and m restrictions and that all variables are binaries, so a simple case differentation can be made on each variably, then this new LP would have at least 2nm variables. For small sized problems this might still numerical possible to be calculated. This huge LP should not be attacked for optimal values in the author's view because of the not avoidable high computing time but searched for good solutions in a effective manner. It should be mentioned that it is possible to use the theory again and to formulate a construction a LP of dimension 4n 2 m which should give better lower bounds then the P comb .
3 Implementation with usage of optimal solutions of the subproblems Putting the thoughts from the previous section together you get the following algorithm described as pseudo-Code to get higher objective values of a MILPinstance with only 0-1 variables: 1: derive P l from given MILP-instance 2: load P l into LP-solver 3: solve P l and save one optimal solution x and the fitting dual solution y 4: for all i, where (x) i is not integer do 5: case j = 1:

6:
add inequality x i ≤ 0 to P l (so getting P i,1 ) 7: solve this LP by usage of the old dual solution y and get y + c i,1 as dual solution 8: case j = 2: 10: add inequality x i ≥ 1 to P l (so getting P i,2 ) 11: solve this LP by usage of the old dual solution y and get y + c i,2 as dual solution 12: if ω i (f i ) > 0 then if Normalization trick is wanted then 17: if 19: else 20: for all r: end if 25: end for 26: build new LP-instance R with all marked i in variables λ i as described in 2.7 27: solve R In first implementation I was not able to use the old solution in lines 7 and 11 effectively. This has quite some impact because of the degeneration of the optimal dual solution in most of the prominent problems. To understand this let's consider you have chosen an optimal y with (y) m > 0 for a problem P . But also an optimalȳ exists with (ȳ) m = 0. Now for all i one c i,j could exist where (y + c i,j ) m = 0. This leads to the situation that no file could be combined ensured by the inequality of R, which deals with the fact that dual variables for inequalities should be positive. But if you had chosen the otherȳ, you would have less problems. As a side-remark it should be noticed that also all P i,j normally then have a degenerate dual solution space. The way to use the old solution y as a starting point for solving P i,j has two benefits: First the optimal solution should be found faster numerically and secondly normally when dealing with degeneracy the above described effect should happen less often. The above algorithm has been implemented with the Open-Source package glpk. In this program all MILP are transformed to be Minimum-problems by exchanging the sign of the objective. So some results on MILP have an extraordinary sign. The problem library MIPLIB2003 has been processed partially getting the results on the following page.
In the given table the column Branches measures the number of variables where branching took place. The actual number of calculated LPs is 2 times more plus the initials LP and the combining LP. The column Degree is equal to i λ i of the optimal value of the combining LP. It gives an idea how much branches can be used at the same time but also in an effective way. The current implementation separates already the normal and the dual LP because of future plans. So we measure both in seconds. Furthermore also the total time for all calculation is presented. The given table only includes those instances, where the program finished within 1 hour. Furthermore for some instances no advantage at all was made, because at no branch there was an increase in both nodes at all. For more investigations these problems might be put out of scope. On the other hand for the instance tr12-30 a quite high lower bound was reached: Starting from 14210 the bound 79695 is reached which is much nearer to the real value at 130596.
Clearly by just viewing the problem the optimal value of ω is 4. The optimal solution of the LP itself is x i,l = 0.5 for i ∈ {1; 2} and l ∈ {1; 2; 3} with objective 3. All dual variables y i,l have also the value 0.5. The next step is to make the case differentiations. Let's concentrate on x i,1 . Either x i,1 = 0 holds (case j = 1) or x i,1 ≥ 1 (case j = 2).

Almost a real one
Maximize ω(x) = x 1 + x 2 + x 3 + x 4 + x 5 and all variables have to be integer. Let i ∈ {1; . . . ; 5}, the optimal dual solution of the LP is simply y i = 1 3 with ω = 5 3 . The optimal solution of the MILP has objective of 1. For example we branch on the two cases x 1 = 0 and x 1 ≥ 1. We get then the following dual solutions: With objective 1 6 λ 1 + 1 6 λ 2 + 1 6 λ 3 + 1 6 λ 4 + 1 6 λ 5 . The optimal solution is λ i = 4 11 and objective is 10 33 . So that we have shown that the maximum in our original MILP is less or equal 5 3 − 10 33 . At this point it is again possible to make a case differentiation on x 1 = 0 or x 1 ≥ 1. If we assume x 1 = 0 the above LP would have the following form: We'll stop the calculation at this point. We could now calculate some ∆ 1 via checking the differences for the resulting normal variables λ i and build a new LP, which would represent the possibility of combining the changes of λ i when doing the case differentiations. By this we would again reach better upper limit for the original problem.
It possible to iterate this method until infinity, but some manual calculations have shown that the real lower limit will never be reached in this way.
The author likes this example pretty much. It shows that non-trivial combining are possible, and that the method can be iterated in a surprising way. But it also shows some limits. The above MILP is easily solved by doing the 4 case differentiations on x 1 and x 2 . Furthermore it is even possible to make another case differentiation on one inequality. It is clear via the first inequality that x 1 = 1 or x 2 = 1 or x 3 = 1 or x 1 = x 2 = x 3 = 0 holds. Via this case differentiation it is seen most quickly seen that the optimal value of the MILP is 1. The author thinks that such case differentiation on inequalities should be investigated as an alternative to the normal branching on one variable especially in the 0-1 MILP-context.

Sidestep: Searching for integrity
Only loosely connected to the rest of the paper we now investigate those MILPs and the derived LPs which have non-degenerate optimal solution space. As for all branching investigations especially in this paper the number of non-integers variables, which are supposed to be integer, should be as little as possible to reduce the running time of an implementation.
Therefor we assume that we have an optimal solution vector x 0 . We just freeze the objective function to the optimal value, so getting an additional equality. We set additional bounds on all integer variables This is a good valid definition also for MILPs which are not binary problems.
In general it might be useful to try out use some bounds like [(x 0 ) n − ǫ] ≤ x n ≤ [(x 0 ) n − ǫ] + 1. This gives some integer variables more freedom to become non-integer to allow other integer to more integer in the general MILP case.
Finally we now define for all integer variables n the objective of the minimization problem to enhance the variables to become integer.
The new vector x 1 is now got by solving this LP to optimality. We now calculate again new c n in the described manner so that we have an iterative process.
With this definition we have a good tool which gives almost integers a good motivation to become integer not hindering others in this process to give up integrity.
Notice that the choice of the c n was done by experiments. It cannot be reasoned yet, why this choice was in the experiment superior to other approaches. Also the convergence of the method has only investigated by experiments. It is imaginable that reducing the number of non-integers might enhance the quality of some heuristic cuts findings, but the author has not received in his limited experiments any valuable result. For sure for the class of this paper in chapter 6 this is not relevant as the cuts are only defined by certain dual values and reduced costs.
Clearly this presented idea was motivated by the feasibility pump [2] to generate integer solutions. We present it also here because the following method was developed in spirit of this easy algorithm.

Measurement of good dual values
We will again concentrate on 2.7. Looking at the inequality there you see that each file eats up certain inequalities (dual values) or variables (reduced costs). So to find good values, you have to search for files and hereby for dual variables who eat less of our stock but still give a good improvement in the objective function. First we have to define what it is the meaning is of eating up the stock of inequalities and variables. Suppose again you have made a case j of case differentiation i with a better dual variable set. Some of the some the ∆ r i,j might be negative, but when the file is glued together by maximizing we suspect that the value ∆ r i will be positive. Anyhow even if it is really negative, quite likely no other case differentiation will need the negativeness. So we have argued to measure all negative ∆ r i,j as 0. As a general approach measure distance to the starting point y 0 we can now define: We also needed D ≥ 0 to make the below algorithm work.
We leave out the problem of setting the d r values, but first use this definition to get better dual values. Therefor we create more artificial variables z r in the dual space. Via z ≥ 0 and z ≥ ∆ r i,j and D = r z r we reflect the definition. The idea is now to subtract D from the objective ω in that way the optimal value of the LP created by the case j of the case differentiation will have the same objective in our new artificial LP as y 0 . Let D 0 i,j be the difference of this solution and ω i,j the increase of the objective. Then we set: So we have found an objective with the desired property.
Via our definitions we have assured that D is always positive. When the new LP is now solved to optimality and point y new i,j is found, it is therefor clear that its optimal value is in the polytope P i,j . Furthermore the following can easily be proved: So in terms of effiency of eating up the stock the new point is better or equal than the first optimal point. When it is equal, then the space P i,j might be often one dimensional. But additionally by our definition we have not given up the wish for good objective gain.
Also this trick can easily be iterated, visible already by our definitions. The algorithm can easily be enhanced that it works on finding better values of files, but this generalizations will not be presented here. Also in an implementation you could use the values of the already manipulated cases of the case differentiation. When an inequality or a variable has been eaten up a bit the new case should have this meal for free.
We now have had some fun with preparing effecient meals of inequalities and variables, but one crucial point of the receipt is still open: the definition of the d r . If you define all d r = 1, then the big l r in 2.7 will get two much attention. Tiny l r , which might always hinder the combining of the files, are overlooked. So the natural choice is to set d r = 1 lr which will give all non-null inequalities and all variables with real reduced costs the same weight. Sadly this theoretically good approach lead in the author implementations to numerical problems. Often the manipulated LP was bad conditioned. So the author suggests to use a lower limit like 0.01 for all d r .
The author has implemented the above algorithm partially, but with some disappointment for him. He didn't manage to use the old optimal solution in the software package glpk, so each manipulated LP had to be solved from scratch. This lead to too long running times. He thinks also that this time increase is only partial because of some missing features of the used software. Using the theoretical good reasoned approach of this section might just be too numerical complex because of the sheer number of added constraints.

Finding quickly the dual values
In the preceding subsection we described a theory to find dual solutions with good objective which could be considered as near to the basic dual solution y 0 . We did this via introducing variables, which measured the distance to the original. Another approach in finding good dual solutions and so files is to use additional inequalities. Depending on the aim this can result in files which fit better to each other or in dual solution which can be calculated very quickly. Suppose you have already made a branching with a file f 1 . Then to combine a second branching with the first you just demand: Speaking in terms of dual inequalities you get lower bounds for those variables y m , which were nonzero in the basic dual solution. Furthermore restrictive dual inequalities which weren't in the solution vector y 0 become in general more restrictive. The benefit of this approach is that using those additional restrictions it is clear that the two branching can fully combined. In terms of 2.7 this means that λ 1 = λ 2 = 1. Naturally the idea can easily be iterated via demanding: Let's do at this point another sidestep. Suppose that both files consist of two cases, which is the normal case for MILPs. You have done the case differentiations to combine these two cases, so you have solved 2 + 2 = 4 calculations. But doing instead a case differentiation on the the 4 cases (2 * 2 = 4), which already enumerate all possible combinations, you would have the same calculation time. But you will have a least better objective increase with these 4 cases than with combining the two case differentation. So for a clever implementation of these sketched algorithms the principle of parallel branching should not followed too strictly. Doing all case differentiations on p cases might be interesting, when 2 p ist still comparable to 2p.
But let's get back to additional restrictions for the dual inequalities. We start with a metaphor: Linear equations describe the nature. When a butterfly flies up in Brazil the emerging circulations won't normally influence the weather in Europe. Speaking in terms of LP an introduction of a new variable in a dual inequality has often only effect in those inequalities, which are strongly bound to the related inequalities. So it is striking thought a neighborhood of a new variable, and to freeze all other variables, which are not in the neighborhood. This should have a big reduction of the running time as a result. If we have good criteria for the neighborhood the objective increase will often be comparable to the objective increase of the new dual inequality without freezing. So it is quite likely that the resulting files might also be effective in terms of the last subsection.
Clearly defining neighborhood by the graph of the inequality system or other means is a complex story. The definition of the neighborhood should also be dependent on the type of the MILP. Suppose you have a good neighborhood definition. Then the technique of freezing most of the dual variables might also be an alternative to the strong branching method, which determines in a branch and cat framework the next variable to branch on. The strong branching relies on a good and steep implementation of the dual simplex, where you use the values of the objective after only some iteration of the Simplex algorithm. It should be noticed that such a steep dual Simplex algorithm is not a prerequisite of the algorithm. So my approach can be used in less advanced packages like glpk to do something similar. This chapter could be described as visionary or even dreamy, anyhow the subject of this paper is to present the author's idea on the subject. To make it complete the author had just add it, otherwise he would always think that his idea have not been presented decently.
6 Application of the theory to produce cuts for the original MILP When thinking of building in the look ahead term of the concurrent branching into a existing branch and cut framework, the dual combining inequality of 2.7 doesn't fit easily. It is striking that instead of that additional dual LP you would like just to have more restrictions in normal space instead. Generation of cuts should be the aim. We'll see in this end of this chapter that this is possible.
We start at that point that we have an optimal dual solution y 0 with only one file f 1 , which describes a case differentiation. We now use a new special form of 2.9, we freeze the f i as linear factors of a scalar λ. Contrary to the special form 2.7 we let y really play the role of dual variables and not fix it to l r -values. So we have as variables the vector y and the scalar λ. Transformed back via dual-dual correspondence this will give us more or less the normal inequalities and equalities plus one additional equality, which will be our cut. But let's stick to the details. We have the following dual inequalities for this special model: The objective is just n c n x n as the normal objective. This looks already interesting, but prior the final transformation to get a cut we must first proof that this system is valid for all integer values. Sadly the proof is very indirect, a direct proof was not discovered by the author.
Before doing the proof we must first study the reuse of files for other basic solutions than the starting one. In 2.7 we had some files, which were tried to be added to some basic solution. If we would have used another solution with other l r -values, we can naturally use the methodology also. Adding the files might still be possible. The only thing which might happen that all λ i in 2.7 have to be 0. Same holds if we have a more strict LP. Then the dual solution has only some more variables, but the original ones are still there.
Remark 6.3 The lookup term via combining files can still be used to a more strict version of the starting normal LP. For incompatible problems it can only be defined, when the missing dual variables (m) of the LP, where the file should be applied, the ∆ m i are negative or 0. This remark also clarifies the usage of the lookup terms for integration in branch and cut frameworks. The file info of a LP remains valid for all descendants and is normally invalid for other descendants of the root LP. Consider you have an integer solution of the LP. Then it is clear that this integer solution is the only optimal solution of a version of the LP, which has been made more strict via adding more inequalities. This more restrictive LP is represented in the dual space by a loosened LP. We still can try to add our file in the dual space. Via this we get the special model 6.1 for the loosened dual inequality.
For this model the optimal objective has to be identical to the dual LP and the normal LP. Otherwise we would prove that the optimal integer solution of the more strict LP has to have bigger objective than the already existing integer solution, which is a contradiction. The optimal dual solution of our loosened LP 6.1 in the dual space is a solution of a more restrictive LP 6.2 than the original one. So we have found an optimal normal solution, which also holds for the more restrictive inequalities. As we had said that the original solution was the only optimal solution, it most be identical to the new one. So the original solution has to fulfill 6.2. So all integer solutions fulfill it. theory for his idea of concurrent branching. Based on this idea he discovered, that it might be reapplied again to normal space.
What's left to be done?
The philosophical statement should be reasoned by some examples. An implementation of the ideas to produce very quickly cuts or lookahead terms should be done, to really measure the usefulness of the theory. Particular for binary problems it would be interesting to generate cuts on inequalities or equations with the discussed technique of fixing most of the dual variables. Furthermore it is most interesting to classify other cuts generation algorithm in our terms or vice versa. Also applying the sketched idea of effectiveness of lookahead terms and so cuts might to other cuts classes might be a fruitful idea.