24.5. 24.5 The use of information obtained from other sources

The method can be sped up by using information provided by further algorithmic tools.

24.5.1. 24.5.1 Application of heuristic methods

The aim of the application of heuristics methods is to obtain feasible solutions. From theoretical point of view to decide if any feasible solution exists is NP-complete as well. On the other hand heuristics can produce feasible solutions in the case of the majority of the numerical problems. The methods to be applied depend on the nature of the problem in question, i.e. pure binary, bounded integer, mixed integer problems may require different methods. For example for pure integer problems local search and Lagrange multipliers can work well. Lagrange multipliers also provide upper bound (in the case of maximization) of the optimal value.

If a feasible solution is known then it is immediately possible to disregard branches based on their bounds. See row 12 of algorithm Branch and Bound . There the branches having not good enough bounds are automatically eliminated. In the case of pure binary problem an explicit objective function constraint can give a lot of consequences as well.

24.5.2. 24.5.2 Preprocessing

Preprocessing means to obtain information on variables and constraints based on algebraic constraints and integrality.

For example if the two constraints of problem (24.36) are summed up then the inequality

is obtained implying that .

Let

be one of the constraints of problem (24.14)-(24.16). Many tests can be based on the following two easy observations:

  1. If the maximal value of the left-hand side of (24.73) of is not greater than the right-hand side of (24.73) then the constraint is redundant.

  2. If the minimal value of the left-hand side of (24.73) if is greater than the right-hand side of (24.73) then it is not possible to satisfy the constraint, i.e. the problem (24.14)-(24.16) has no feasible solution.

If under some further restriction the second observation is true then the restriction in question can be excluded. A typical example is that certain variables are supposed to have maximal/minimal possible value. In this way it is possible to fix a variable or decrease its range.

Lagrange relaxation can be used to fix some variables, too. Assume that the optimal value of Problem (24.22) and (24.16) is under the further condition that must take the value . If is the objective function value of a known feasible solution and then can not take value . Further methods are assuming that the LP relaxation of the problem is solved and based on optimal dual prices try to fix the values of variables.