Integer Programing: Integer Programing
Linear Programming Assumptions: Linear Programming Assumptions • Proportionality – a change in a variable result in a proportionate change in that variable’s contribution to the value of the function • Additivity – the function value is the sum of the contributions of each term • Divisibility – The decision variables can be divided into non-integer values, taking on fractional values Integer programming is used if the divisibility assumption does not hold
Integer Programming: Integer Programming Optimization of a linear objective function Subject to linear constraints, non negativity conditions Integer value conditions (Can handle non-linear problems
IP Problem Classification: IP Problem Classification • Pure integer IP problem – in which all variables are integer • Mixed-integer IP problem – involves some integer and some continuous variables • Zero-one IP problem - in which the integer variables are restricted to either zero or one – pure zero-one IP problems – all variables are zero-one – mixed zero-one IP problems - containing both zero-one and continuous variables
Why Integer Programming: Why Integer Programming Allows to depict discontinuous decision variables – acquisition of machines, hired labor or animals Allows modeling of fixed costs, logical conditions, and discrete levels of resources
Slide 6: Advanced algorithms for solving integer linear programs include: cutting-plane method branch and bound branch and cut branch and price
Branch and Bound Algorithm: Branch and Bound Algorithm Starts with LP solution • imposes constraints to force the LP solution to become an integer solution • constraints are upper and lower bounds on variables. Branch and bound solution procedure generates two problems (branches) after each LP solution One must decide – which variable to branch upon and – which problem to solve (branch to follow).
Slide 8: Branch and bound approach is the most commonly used general purpose IP solution algorithm. • However, its use can be expensive. – Often the branch and bound algorithm will come up with near optimal solutions quickly but will then spend a lot of time verifying optimality
BRANCH AND BOUND: BRANCH AND BOUND Branch and bound ( BB or B&B ) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse , by using upper and lower estimated bounds of the quantity being optimized.
Slide 10: A branch-and-bound procedure requires two tools. The first one is a splitting procedure that, given a set S of candidates, returns two or more smaller sets whose union covers S . Note that the minimum of f ( x ) over S is , where each v i is the minimum of f ( x ) within S i . This step is called branching , since its recursive application defines a tree structure (the search tree ) whose nodes are the subsets of S
Slide 11: Another tool is a procedure that computes upper and lower bounds for the minimum value of f ( x ) within a given subset of S . This step is called bounding .
Slide 12: The key idea of the BB algorithm is: if the lower bound for some tree node (set of candidates) A is greater than the upper bound for some other node B , then A may be safely discarded from the search. This step is called pruning , and is usually implemented by maintaining a global variable m (shared among all nodes of the tree) that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than m can be discarded.
APPLICATIONS : APPLICATIONS Knapsack problem Integer programming Nonlinear programming Traveling salesman problem (TSP) Quadratic assignment problem (QAP) Maximum satisfiability problem (MAX-SAT) Nearest neighbor search (NNS) Cutting stock problem False noise analysis (FNA)