Reconnect 04 Introduction to Integer Programming

1670 days ago, 607 views
PowerPoint PPT Presentation
Slide 2. Whole number programming (IP). MinSubject to:Can likewise have imbalances in either bearing (slack variables):If , then this is a blended number system (MIP)Linear programming (LP) has no integrality requirements (in P)IP (effortlessly) communicates any NP-complete issue.

Presentation Transcript

Slide 1

Reconnect '04 Introduction to Integer Programming Cynthia Phillips, Sandia National Laboratories

Slide 2

Integer programming (IP) Min Subject to: Can likewise have disparities in either bearing (slack factors): If , then this is a blended whole number program (MIP) Linear programming (LP) has no integrality requirements (in P) IP (effortlessly) communicates any NP-finish issue

Slide 3

Terminology In this setting programming implies deciding. Driving terms say what kind: (Pure) Integer programming: all whole number choices Linear programming Quadratic programming: quadratic target work Nonlinear programming: nonlinear imperatives Stochastic programming: limited likelihood dissemination of situations Came from operations look into (handy streamlining discipline) Computer programming (by somebody) is required to illuminate these.

Slide 4

Decisions The IPs I've experienced practically speaking include either Allocation of rare assets Study of a characteristic framework Computational science Mathematics Maybe amid or after this course, you can add to the rundown

Slide 5

Integer Variables Use (twofold factors) to model: Yes/no choices Disjunctions Logical conditions Piecewise straight capacities (this not canvassed in this address)

Slide 6

General Integer Variables Use general whole number factors to pick various resolute protests, for example, the quantity of planes to deliver Integer range ought to be little (e.g. 1-10) Computational tractability Larger reaches might be all around approximated by sound factors (number of sacks of potato chips to create)

Slide 7

Example: Binary Knapsack Given arrangement of articles 1..n aggregate weight W, thing weight/measure w i , esteem v i

Slide 8

Example: Shortest-Path Network Interdiction Delay an enemy traveling through a system. Foe moves begin target along a most limited way (in most pessimistic scenario) Path length = aggregate of edge lengths. Measure of time, introduction, and so on 5 6 Target 3 1 Start 2 5 1 4 Shortest Path Length: 8

Slide 9

Example: Shortest-Path Network Interdiction Defender obstructs the interloper by paying to build edge lengths. Objective: Maximize the subsequent most brief way. 5 6 Target 3 1 Start 2 +1 +2 5 1 4 Shortest Path Length: 11

Slide 10

Path Interdiction Mixed-Integer Program Graph G = (V,E) Edge lengths for edge (u,v) Can expand length of (u,v) by  uv at cost c uv Budget B Variables: d u : most brief separation from begin s to hub u

Slide 11

Path Interdiction Integer Program Objective: amplify the briefest way to the objective boost d t Subject to: Path to the begin has length 0: d s = 0 Calculate a most limited way length: Respect the financial plan: u +  uv v

Slide 12

Modeling Dependent Decisions Suppose x,y are two double factors that speak to a choice (where 1 signifies "yes" and 0 signifies "no") The imperative permits x to be "yes" just if y is "yes"

Slide 13

Example: Unconstrained Facility Location Given potential office areas, n clients to be served c j = cost to construct office j h ij = cost to meet all of client i's request from office j Sometimes it's OK to fulfill clients from various offices:

Slide 14

Formulation is truly critical practically speaking Unconstrained office area Could aggregate limitations over all clients i to get: Recall n is the quantity of clients. Still requires an office is worked before utilize (IPs are equal at optimality) But, for 40 clients, 40 offices, irregular costs First plan unravels in 2 seconds Second definition explains in 53,121 seconds (14.75 hours)

Slide 15

What improves one detailing to such an extent? Understanding this completely is an open issue. Some execution contrasts can be clarified by the way IPs are comprehended by and by branch-and-bound-like calculations: the LP unwinding

Slide 16

Recall Integer Programming (IP) Min Subject to:

Slide 17

Linear programming (LP) unwinding of an IP Min Subject to: LP can be explained proficiently (in principle and practice) Relaxation = expelling requirements All achievable IP arrangements are attainable LP gives a lower bound

Slide 18

Linear Programming Geometry The answers for a solitary disparity shape a half space (in n-dimensional space) possible

Slide 19

Linear Programming Geometry Intersection of all the direct (in)equalities frame a raised polytope For effortlessness, we'll generally accept polytope is limited doable

Slide 20

IP Geometry Feasible whole number focuses frame a cross section inside the LP polytope

Slide 21

IP Geometry The arched body of this grid frames the whole number polytope

Slide 22

IP/LP Geometry A "decent" definition keeps this locale little Every hub for which the LP bound is lower than the number ideal must be handled (e.g. extended)

Slide 23

IP/LP Geometry A "decent" detailing keeps this area little One measure of this is the Integrality Gap : Integrality crevice = max examples I (IP (I))/(LP(I))

Slide 24

Unconstrained Facility Location Revisited Given potential office areas, clients to be served c j = cost to manufacture office j h ij = cost to meet all of client i's request from office j

Slide 25

How the weaker LP "cheats" Using Allows the LP to totally fulfill client i with office j ( y ij = 1) even with x j = 1/n . With these limitations: If x i = 1/n, then y ij <= 1/n

Slide 26

Can't we simply round the LP Solution? Not by and large practical If (inexplicably) it is achievable, it's not by and large great

Slide 27

1 4 2 3 7 5 6 Example: Maximum Independent Set Find a greatest size arrangement of vertices that have no edges between any match

Slide 28

1 4 2 3 7 5 6 Example: Maximum Independent Set

Slide 29

1 4 2 3 7 5 6 Example: Maximum Independent Set The zero-data arrangement ( v i = .5 for all i ) is attainable and it's ideal if the ideal MIS has estimate at most |V|/2. Adjusting everything (up) is infeasible. 1/2 1/2 1/2 1/2 1/2 1/2 1/2

Slide 30

Can't we anticipate the grid onto the goal angle? Elusive an attainable answer for venture (NP-finish!) Make the goal a limitation and do parallel inquiry This is a considerable measure harder in n measurements than it would appear that in 2 angle

Slide 31

Perfect details Sometimes fathoming a LP is ensured to give a number arrangement All polytope corners have whole number coefficients (actually number) Sometimes just for particular destinations (e.g. )

Slide 32

Perfect Formulation Example: Minimum Cut Special hubs s and t Each edge e has limit u e . Set of edges S has limit Partition vertex set V into S,T where A cut is the edges (u,v) to such an extent that Find a cut with least limit 12 1 4 Capacity u e 27 2 s 5 9 3 1 20 t 8 2 5 2

Slide 33

Perfect Formulation Example: Minimum Cut IP Helper factors y e = 1 if e is in the cut and 0 generally The y factors will be indispensable if the v factors are.

Slide 34

Total Unimodularity The base cut network (potentially with slack factors) is absolutely unimodular (TU) : all subdeterminants (counting the grid passages) have esteem 0, 1, or - 1. All corner arrangements x fulfill Ax=b By Kramer's manage x will be indispensable Network lattices (contiguousness grids of diagrams) are TU. Nemhauser and Wolsey (Integer and Combinatorial Optimization, Wiley, 1988) give some adequate conditions for a lattice to be TU. Note: if a framework is TU, there is dependably an effective combinatorial calculation to take care of the issue (not really self-evident)

Slide 35

Total Unimodularity is Fragile Example: Network Interdiction Expend a restricted spending plan to maximally harm the vehicle limit of a system

Slide 36

Network Flow 11/12 1 4 Source(s) s, sink (buyers) t Capacity (base number) Flow (beat number) Maximize spill out of s to t obeying Capacity imperatives on edges Conservation requirements on all hubs other than s,t 11/27 0/5 9/9 5/5 2/2 s 3 1/1 8/20 t 3/3 2 5 2/2/8

Slide 37

Network Interdiction 11/12 1 4 Each edge e now has an obliteration cost d e (cost to expel e ; accept direct) Budget B Expend at most B expelling (bits of) edges in the system so coming about max stream is limited 11/27 0/5 9/9 5/5 2/2 s 3 1/1 8/20 t 3/3 2 5 2/2/8

Slide 38

Network Interdiction By LP duality (we'll see later) value of max stream = estimation of min cut So min assaults max stream = min assaults min slice Pay to thump out transport limit from s to t 12 1 4 27 5 s 5 9 2 3 1 20 t 8 2 5 2

Slide 39

A Mixed Integer Program for Network Inhibition Based on min-slice LP Find best slice to assault Decision factors put vertices on the s or t side as before All edges going over the cut must be devastated (devour spending plan) or add to lingering cut limit 0 1 t s

Slide 40

Network Inhibition IP Helper factors y e = percent of an edge in cut that is not evacuated z e = percent of an edge in the cut that is pulverized

Slide 41

Total Unimodularity is Fragile The lattice is still TU without the spending limitation Adding the spending requirement makes the issue unequivocally NP-finish No known polynomial-time guess calculations Still has some exceptionally pleasant structure that gives a pseudo-estimate Pseudo-estimate may give a superoptimal arrangement that marginally surpasses the financial plan or it could give a genuine estimation

Slide 42

Modeling Sets Given a set T, implies select no less than 1 component of T Making beyond any doubt no less than one nearby distribution center has stock for every client implies select at most 1 component of T Conflicts (e.g. demonstrated by a most extreme autonomous set issue) Resource imperatives implies select precisely 1 component of T Time filed planning factors x jt , plan jo