logging in or signing up integer programming jigs_1806 Download Post to : URL : Related Presentations : Let's Connect Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 273 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: November 28, 2011 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Integer Programing: Integer ProgramingLinear 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 variablesWhy 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 resourcesSlide 6: Advanced algorithms for solving integer linear programs include: cutting-plane method branch and bound branch and cut branch and priceBranch 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 optimalityBRANCH 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 SSlide 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) You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.