0

0

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.

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

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

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.

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

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

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)

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

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

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

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

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

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"

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:

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)

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

Recall Integer Programming (IP) Min Subject to:

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

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

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

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

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

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)

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))

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

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

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

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

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

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

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

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. )

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

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.

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)

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

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

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

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

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

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

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

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

SPONSORS

No comments found.

SPONSORS

SPONSORS