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)

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.