1 of 26

TNK104 Applied Optimization

LP and IP

Lecture 4

based on the slides provided by Nikolaos Pappas

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

2 of 26

TNK104 Applied Optimization I

LP Basics LP standard form

Special case of convex optimization
The solution space is a polyhedron/polytope
An LP can be

Feasible with bounded optimum
Infeasible
Unbounded optimum

3 of 26

LP Basics (cont’d)

TNK104 Applied Optimization I

If an LP is feasible and has bounded optimum, then (at least one) optimum is located at an extreme point. Why? (see self-study material on LP)
An LP can be solved efficiently, both in theory and practice

Simplex method
Ellipsoid algorithm (in P!)
Interior point methods

Feasibility problem (objective function is not important)

4 of 26

TNK104 Applied Optimization I

A Two-dimensional Example

x₂

Objective

Setting two variables to zeros

→ Solution of an equation system!

This type of solutions are called basic solutions

5 of 26

TNK104 Applied Optimization I

A Two-dimensional Example

6 of 26

TNK104 Applied Optimization I

Basic Solution in Matrix Notation

7 of 26

The Primal Simplex Method

TNK104 Applied Optimization I

8 of 26

TNK104 Applied Optimization I

Reduced Cost

Indicates the unit change in the objective function when a variable changes its value from the current basic solution
Minimization/maximization: Choose a variable having negative/positive

reduce cost as the incoming variable

9 of 26

TNK104 Applied Optimization I

LP Duality

Primal

Dual

Infeasible primal unbounded dual

Unbounded dual Infeasible primal

Both problems infeasible

10 of 26

IP (integer) and MIP (mixed-integer) Model

TNK104 Applied Optimization I

Some variables are integers
Non-convex, much harder to tackle than LP
LP relaxation: relax integer condition! gives a lower/upper bound
Integrality gap: The difference (if any) between the IP optimum and LP optimum

11 of 26

The Convex Hull

TNK104 Applied Optimization I

Convex hull: The minimum convex set containing all integer solutions

All extreme points of the convex hull are integral

→ Solve ILP = Solve the LP over the convex hull!

Sometimes the convex hull = LP relaxation
In general, an explicit description of the facets defining the convex hull remains a dream

Objective

12 of 26

The Convex Hull (cont’d)

TNK104 Applied Optimization I

The structure of the convex hull can be very complex
However, even partial knowledge of the convex hull is useful
Valid inequality (aka cut)

Valid = does not cut off any part of the convex hull
Cut generation (aka separation) is often hard

Objective

LP optimum

New LP optimum

13 of 26

Acknowledgement: Numerical example from L. Wolsey, Integer Programming, John Wiley & Sons, 1998

TNK104 Applied Optimization I

Example of Structured Valid Inequality: Cover Inequalities

Consider the set of solutions defined by

14 of 26

Cover Inequalities: A General Definition

TNK104 Applied Optimization I

Another example: Cover inequalities for Knapsack problem

15 of 26

Separation Problem

TNK104 Applied Optimization I

We are only interested in finding useful valid inequalities

Does the current fractional point (LP) violate some valid inequality?

that is, is there a valid inequality separating the point from the convex full?

16 of 26

Separation Problem (cont’d)

TNK104 Applied Optimization I

17 of 26

Cutting Plane Method: A Summary

TNK104 Applied Optimization I

Solve the LP
Separation of valid inequalities, preferably facets
Add the inequalities and solve the new LP
Repeat

Still fractional: Construct an integer solution (e.g., rounding heuristic)

Q1: Is it always doable to find a cut violated by a fractional LP solution?

Q2: Is there a cutting plane method that is guaranteed to converge in finite number of steps? Q3: If the answers to Q1 and Q2 are positive, would a cutting plane method alone be sufficient?

18 of 26

Branch and Bound (B&B): Underlying Idea

TNK104 Applied Optimization I

Divide and conquer
Branching: Partition the original solution space
Bounding

Solve a relaxation of the ILP (e.g., LP relaxation)
Procedures for obtaining integer solutions

Fathoming

19 of 26

TNK104 Applied Optimization I

B&B: A Small Example

20 of 26

TNK104 Applied Optimization I

B&B: A Small Example (cont’d)

21 of 26

Branch and Bound (B&B): Summary

TNK104 Applied Optimization I

The solution process is represented by a tree

Node = a portion of the solution space
Optimistic bound via some relaxation
Primal bounds (integer solutions) by heuristics

A node can be fathomed if

Relaxation not feasible (thus no feasible integer point)
Integer optimum found for this node
The optimistic bound is not better than the overall best primal bound

→ Implicit enumeration

Branching

Branching ^Branching

22 of 26

Solver

TNK104 Applied Optimization I

Software implementation methods for solving optimization models
User interface + optimization engine
Optimal or approximate solutions (problem size/difficulty, time, memory. . .)

Optimization engine
Simplex method for LP
Interior-point methods for LP
Branch and bound/cut for ILP/MIP

Non-linear optimization methods
. . .

Command line interface GUI

Callable library (e.g., C++)

Numerical model

Solution and related information

23 of 26

Solver Classification

TNK104 Applied Optimization I

General-purpose or specialized (e.g., network flow problems)
Model type

LP, ILP, MIP, convex NLP
General NLP, global optimization, etc.
Constraint programming

License

Commercial (academic license typically available, sometimes free): IBM CPLEX, GUROBI solver, MINOS, Xpress-solvers, LINDO, etc.
Free (often open source): SOPLEX, lpsolve, GLPK, COIN-OR solvers, NEOS server, etc.