Gutin, G. In: Gutin, G. Kluwer, Dordrecht Google Scholar. Johnson, D. Krentel, M. Google Scholar. Orlin, J. Papadimitriou, C. Ramaswamy, R. Schrijver, A. Schulz, A. This is a preview of subscription content, log in to check access. Richard Kipp Martin 1 1. Personalised recommendations.
Cite chapter How to cite? Since MIP and CP problems are non-convex , they must be solved by some kind of systematic and potentially exhaustive search.
The "classic" method for solving these problems is called Branch and Bound. This method begins by finding the optimal solution to the "relaxation" of the problem without the integer constraints via standard linear or nonlinear optimization methods. If in this solution, the decision variables with integer constraints have integer values, then no further work is required. If one or more integer variables have non-integral solutions, the Branch and Bound method chooses one such variable and "branches," creating two new subproblems where the value of that variable is more tightly constrained.
These subproblems are solved and the process is repeated, until a solution that satisfies all of the integer constraints is found. Alternative methods, such as genetic and evolutionary algorithms, randomly generate candidate solutions that satisfy the integer constraints. Such initial solutions are usually far from optimal, but these methods then transform existing solutions into new candidate solutions, through methods such as integer- or permutation-preserving mutation and crossover , that continue to satisfy the integer constraints, but may have better objective values.
This arises due to the fact that in constructing the above example I decided to make the situation as simple as possible. In general we might well have more than one fractional variable at a tree node and so we face a decision as to which variable to choose to branch on. A simple rule for deciding might be to take the fractional variable which is closest in value to 0. Many of the computational advances in IP optimal solution methods e.
Often the key to making successful use of such packages for any particular problem is to put effort into a good formulation of the problem in terms of the variables and constraints. By this we mean that for any particular IP there may be a number of valid formulations. Deciding which formulation to adopt in a solution algorithm is often a combination of experience and trial and error.
Constraint logic programming CLP , also called constraint programming , which is essentially branch and bound but without the bound, can be of use here if:. The branch and bound method is the method used by the package. If you do not have access to an integer programming package one package albeit with restricted capacity is available free here. Below we solve the capital budgeting problem with the Solver add-in that comes with Microsoft Excel. If you click here you will be able to download an Excel spreadsheet called ip.
Take this spreadsheet and look at Sheet A. You should see the problem we considered above set out as:. Here we have set up the problem with the decisions the zero-one variables being shown in cells B3 to B6. I will mention in the lecture if there is time a number of IP problems I have been involved with:.
Essentially the only effective approach here is to run a general purpose optimal algorithm and terminate early e. If we are dealing with one specific type of IP then we might well be able to develop a special purpose solution algorithm designed for just this one type of IP that is more effective computationally than the general purpose branch and bound method given earlier. These are typically tree search approaches based upon generating bounds via:.
Such algorithms, being different for different problems, are really beyond the scope of this course but suffice to say:. A large amount of academic effort in this field is devoted to generating methods that out-perform previous methods for the same problem. On a personal note this is an area with which I am familiar and special purpose algorithms can be very effective e.
They can be very successful compared with general purpose optimal algorithms perhaps an order of magnitude or more in terms of the size of problem that can be solved. You should be clear though why a special purpose optimal algorithm can be so computationally more effective than a general purpose optimal algorithm, it is because you have to put intellectual effort into designing the algorithm!
With regard to heuristics we have a number of generic approaches in the literature, for example:. All of these generic approaches however must be tailored for the particular IP we are considering.
In addition we can design heuristics purely for the particular problem we are considering problem-specific heuristics. Heuristics for IP's are widespread in the literature and applied quite widely in practice.
0コメント