Example: biology

MixedIntegerLinearProgramming

Mixed Integer Linear ProgrammingCombinatorial Problem Solving (CPS)Javier Larrosa Albert Oliveras Enric Rodr guez-CarbonellMay 3, 2021 Mixed Integer Linear Programs2 / 61 Amixed integer linear program(MILP, MIP) is of the formmincTxAx=bx 0xi Z i I If all variables need to be integer,it is called a(pure) integer linear program(ILP, IP) If all variables need to be0or1(binary, boolean),it is called a0 1linear programComplexity: LP vs. IP3 / 61 Including integer variables increases enourmously the modeling power,at the expense of more complexity LP s can be solved inpolynomial timewith interior-point methods(ellipsoid method, Karmarkar s algorithm) Integer Programming is anNP-hardproblem. So: There isno known polynomial-time algorithm There arelittle chancesthat one will ever be found Even small problems may be hard to solve What follows is one of the many approaches(and one of the most successful) for attacking IP sLP Relaxation of a MIP4 / 61 Given a MIP(IP)mincTxAx=bx 0xi Z i Iitslinear relaxationis the LP obtained by dropping integrality constraints:(L)

Branch&Bound 7/61 Assume variables are bounded, i.e., have lower and upper bounds Let P0 be the initial problem, LP(P0)be the LP relaxation of P0 If in optimal solution of LP(P0)all integer variables take integer values then it is also an optimal solution to P0 Else Let xj be integer variable whose value βj at optimal solution of LP(P0)is such that βj ∈Z.

Fullscreen Download

Tags:

  Bounded, Mixedintegerlinearprogramming

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Advertisement

Transcription of MixedIntegerLinearProgramming

1 Mixed Integer Linear ProgrammingCombinatorial Problem Solving (CPS)Javier Larrosa Albert Oliveras Enric Rodr guez-CarbonellMay 3, 2021 Mixed Integer Linear Programs2 / 61 Amixed integer linear program(MILP, MIP) is of the formmincTxAx=bx 0xi Z i I If all variables need to be integer,it is called a(pure) integer linear program(ILP, IP) If all variables need to be0or1(binary, boolean),it is called a0 1linear programComplexity: LP vs. IP3 / 61 Including integer variables increases enourmously the modeling power,at the expense of more complexity LP s can be solved inpolynomial timewith interior-point methods(ellipsoid method, Karmarkar s algorithm) Integer Programming is anNP-hardproblem. So: There isno known polynomial-time algorithm There arelittle chancesthat one will ever be found Even small problems may be hard to solve What follows is one of the many approaches(and one of the most successful) for attacking IP sLP Relaxation of a MIP4 / 61 Given a MIP(IP)mincTxAx=bx 0xi Z i Iitslinear relaxationis the LP obtained by dropping integrality constraints:(LP)mincTxAx=bx 0 Can we solveIPby solvingLP?

2 By rounding?Branch & Bound5 / 61 The optimal solution ofmaxx+y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zis(x, y) = (1,2), with objective3 The optimal solution of its LP relaxationis(x, y) = (4, ), with No direct way of getting from(4, )to(1,2)by rounding! Something more elaborate is needed:branch & boundBranch & Bound6 / 61yxy 0maxx+y(0,1)(1,2)x 0(4, ) 8x+ 10y 13 2x+ 2y 1 Branch & Bound7 / 61 Assumevariables are bounded , , have lower and upper bounds LetP0be the initial problem,LP(P0)be the LP relaxation ofP0 If in optimal solution ofLP(P0)all integer variables take integer valuesthen it is also an optimal solution toP0 Else Letxjbe integer variablewhose value jat optimal solution ofLP(P0)is such that j6 :=P0 xj j P2:=P0 xj j feasibleSols(P0) = feasibleSols(P1) feasibleSols(P2) Idea: solveP1, solveP2and then take the bestBranch & Bound8 / 61 Letxjbe integer variablewhose value jat optimal solution ofLP(P0)is such that j6 of the problemsP1.

3 =P0 xj j P2:=P0 xj j can besolved recursively We can build abinary tree of subproblemswhose leaves correspond topendingproblems still to be solved This procedure terminates as integer vars have finite bounds and,at each split, the domain ofxjbecomes strictly smaller IfLP(Pi)has optimal solution where integer variables take integer valuesthen solution is stored IfLP(Pi)is infeasible thenPican be discarded(pruned, fathomed)Example9 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y ZExample9 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y ZExample10 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 End====================================================================CPLEX> optimizePrimal simplex - Optimal: Objective = - +00 Solution time = sec.

4 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5 Example11 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5 Example12 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsy >= 5 End===================================== ===============================CPLEX> optimizeBound infeasibility column x .Presolve time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example13 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5 Example13 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5 Example14 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsy <= 4 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

5 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3 Example15 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3 Example16 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx >= 4y <= 4 End====================================================================CPLEX> optimizeRow c1 infeasible, all entries at implied time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example17 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3 Example17 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3 Example18 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 3y <= 4 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

6 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4 Example19 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4 Example20 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 3y = 4 End====================================================================CPLEX> optimizeBound infeasibility column x .Presolve time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example21 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4 Example21 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4 Example22 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 3y <= 3 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

7 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2 Example23 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2 Example24 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx = 3y <= 3 End====================================================================CPLEX> optimizeBound infeasibility column y .Presolve time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example25 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2 Example25 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2 Example26 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 2y <= 3 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

8 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3 Example27 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3 Example28 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 2y = 3 End====================================================================CPLEX> optimizeBound infeasibility column x .Presolve time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example29 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3 Example29 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3 Example30 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 2y <= 2 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

9 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3x 2x 1 Example31 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3x 2x 1 Example32 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx = 2y <= 2 End====================================================================CPLEX> optimizeBound infeasibility column y .Presolve time = sec. ( ticks)Presolve - time = time = ticks ( ticks/sec)Example33 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3x 2x 1 Example33 / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3x 2x 1 Example34 / 61 Min - x - ySubject To-2 x + 2 y >= 1-8 x + 10 y <= 13 Boundsx <= 1y <= 2 End====================================================================CPLEX> optimizeDual simplex - Optimal: Objective = - +00 Solution time = sec.

10 Iterations = 0 (0)Deterministic time = ticks ( ticks/sec)CPLEX> display solution variables xVariable Name Solution Valuex > display solution variables yVariable Name Solution Valuey / 61min x y 2x+ 2y 1 8x+ 10y 13x, y 0x, y Zy 4y 5x 4x 3y 3y 4x 3x 2y 2y 3x 2x 1 Pruning in Branch & Bound36 / 61 We have already seen that if relaxation is infeasible,the problem can be pruned Now assume an (integral) solution has been previously found If solution has costZthen any pending problemPjwhose relaxation hasoptimal value Zcan be ignored, sincecost(Pj) cost(LP(Pj)) ZThe optimum will not be in any descendant ofPj! Thiscost-based pruningof the search tree has a huge impacton the efficiency of Branch & BoundBranch & Bound: Algorithm37 / 61S:={P0}/* set of pending problems */Z:= + /* best cost found so far */whileS6= doremovePfromSsolveLP(P)ifLP(P)is feasiblethen/* if unfeasiblePcan be pruned */let be optimal basic solution ofLP(P)if satisfies integrality constraintsthenifcost( )< Zthenstore ; updateZelseifcost(LP(P)) Zthen continue/*Pcan be pruned */letxjbe integer variable such that j6 ZS:=S {P xj j , P xj j }returnZHeuristics in Branch & Bound38 / 61 Possible choices in Branch & Bound Choice of thepending problem Depth-firstsearch Breadth-firstsearc

Show more

Documents from same domain

The R Book - UPC Universitat Polit&#232;cnica de Catalunya

The R Book - UPC Universitat Politècnica de Catalunya

www.cs.upc.edu

Detailed Contents Preface xxiii 1 Getting Started 1 1.1 How to use this book 1 1.1.1 Beginner in both computing and statistics 1 1.1.2 Student needing help with project work 2

  Book, The r book

Introduction to Verilog

Introduction to Verilog

www.cs.upc.edu

Introduction to Verilog Oct/1/03 3 Peter M. Nyasulu and J Knight Primitive logic gates are part of the Verilog language. Two properties can be specified,drive_strengthand delay. Drive_strengthspecifies the strength at the gate outputs.The strongest output is a direct connection to a source, next

  Introduction

&#191;Qu&#233; es la Inteligencia Artificial?

¿Qué es la Inteligencia Artificial?

www.cs.upc.edu

Bases de la Inteligencia Artificial Ingeniería computacional • Para la existencia de la IA es necesario un mecanismo para soportarlo (hardware) • También son necesarias herramientas para desarrollar programas de IA Lingüística • Chomsky: representación del conocimiento, gramática de la lengua • Lingüística computacional 7

  Artificial, Herramientas, Inteligencia, Es la inteligencia artificial

PANTONE color bridge CMYK PC Page: 1 of 14

PANTONE color bridge CMYK PC Page: 1 of 14

www.cs.upc.edu

pantone® color bridge™ cmyk pc page: 2 of 14 pantone 155 pc c:0 m:12 y:32 k:0 pantone 156 pc c:0 m:24 y:49 k:0 pantone 157 pc c:0 m:44 y:71 …

  Bridge, Pages, Pantone, Cmyk, 1 of 14, Bridge cmyk pc page

Introduction to Programming (in C++)

Introduction to Programming (in C++)

www.cs.upc.edu

•Language: C++ . High-level language • Computers understand very low-level instructions (machine language). • Software is usually constructed using high-level languages. –Higher productivity –Better readability –Simpler debugging –But …

Normalizaci&#243;n de Bases de Datos y T&#233;cnicas de dise&#241;o

Normalización de Bases de Datos y Técnicas de diseño

www.cs.upc.edu

Antes de definir el cuarto nivel de F/N, veremos tres tipos de relaciones entre los datos: uno-a-uno, uno-con-varios y varios-con-varios. Mira la tabla usuarios en el Primer Nivel de F/N del ejemplo de arriba. Por un momento imaginámos que ponemos el campo url en una tabla separada, y cada vez que introducimos

  Base, Primer, Otda, Nivel, Nivel de, Primer nivel de, Normalizaci, 243 n de bases de datos

An Introduction to Cooperative Game Theory

An Introduction to Cooperative Game Theory

www.cs.upc.edu

De nitions Stability notions Other solution concepts Subclasses TU characteristic function games Outcomes Imputations Non-Cooperative versus cooperative Games Non-cooperative game theory model scenarios where players cannot make binding agreements. Cooperative game theory model scenarios, where agents can bene t by cooperating, and

  Notions

Related documents

Chapter 8 Bounded Linear Operators on a Hilbert Space

Chapter 8 Bounded Linear Operators on a Hilbert Space

www.math.ucdavis.edu

Thus, every bounded linear functional is given by the inner product with a xed vector. We have already seen that ’y(x) = hy;xi de nes a bounded linear functional on H for every y 2 H. To prove that there is a unique y in H associated with a given linear functional, suppose that ’y1 = ’y2. Then ’y1(y) = ’y2(y) when y = y1 y2,

  Linear, Chapter, Operator, Bounded, Hilbert, Chapter 8 bounded linear operators on a hilbert, Bounded linear

Lecture 13 Linear quadratic Lyapunov theory

Lecture 13 Linear quadratic Lyapunov theory

web.stanford.edu

• the sublevel sets are ellipsoids (and bounded) • V(z) = zTPz = 0 ⇔ z = 0 boundedness condition: if P > 0, Q ≥ 0 then • all trajectories of x˙ = Ax are bounded (this means ℜλi ≤ 0, and if ℜλi = 0, then λi corresponds to a Jordan block of size one) • the ellipsoids {z | zTPz ≤ a} are invariant Linear quadratic Lyapunov ...

  Linear, Bounded, Lyapunov

SOLUTION OF LINEAR PROGRAMMING PROBLEMS

SOLUTION OF LINEAR PROGRAMMING PROBLEMS

www.math.tamu.edu

If S is bounded then P has both a maximum and minimum value on S If S is unbounded and both a and b are nonnegative, then P has a minimum value on S provided that the constraints defining S include the inequalities x≥ 0 and y≥ 0. If S is the empty set, then the linear programming problem has no solution; that is, P has neither

  Linear, Bounded

Lecture 6 1 The Dual of Linear Program

Lecture 6 1 The Dual of Linear Program

theory.stanford.edu

What is surprising is that, for bounded and feasible linear programs, there is always a dual solution that certi es the exact value of the optimum. Theorem 5 (Strong Duality) If either LP 1 or LP 2 is feasible and bounded, then so is the other, and opt(LP 1) = opt(LP 2) To summarize, the following cases can arise: If one of LP 1 or LP

  Linear, Bounded

Covariance and Correlation Math 217 Probability and ...

Covariance and Correlation Math 217 Probability and ...

mathcs.clarku.edu

dard deviations, the correlation becomes bounded ... kind of thing that goes on in linear algebra. In fact, it is the same thing exactly. Take a set of real-valued random variables, not necessarily inde-pendent. Their linear combinations form a vector space. Their covariance is …

  Linear, Bounded

MATH 304 Linear Algebra

MATH 304 Linear Algebra

www.math.tamu.edu

Linear Algebra Lecture 20: Inner product spaces. Orthogonal sets. Norm The notion of norm generalizes the notion of length of a vector in Rn. Definition. Let V be a vector space. ... where w is bounded, piecewise continuous, and w > 0 everywhere on [a,b]. w is called the weight function. Theorem Suppose hx,yi is an inner product on a vector ...

  Linear, Bounded

Linear Programming I: Maximization - Sam Baker

Linear Programming I: Maximization - Sam Baker

sambaker.com

Linear programming is constrained optimization, where the constraints and the objective function are all linear. It is called "programming" becaus e the goal of the calculations help you choose a "program" of ... corner, bounded by the constraints. 4. Find the highest value isoprofit line that touches the feasible region. Imagine moving that 3x ...

  Linear, Bounded

Chapter2

Chapter2

www.math.ucdavis.edu

A function f is bounded from above on A if supAf is finite, bounded from below on A if infAf is finite, and bounded on A if both are finite. Inequalities and operations on functions are defined pointwise as usual; for example, if f,g : A → R, then f ≤ g …

  Bounded

Related search queries

Chapter 8 Bounded Linear Operators on a Hilbert, Bounded linear, Linear, Lyapunov, Bounded