New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
business
operations research an introduction

Optimization In Operations Research 2nd Edition Ronald Rardin - Solutions

Military commanders are planning the command structure for 6 new radar stations.Three commanders will each be in charge of two of the stations. The following table shows the projected cost (in millions of dollars) of building the necessary communication links to connect jointly commanded
Awesome Advertising manages the television promotion of a variety of products. In the next few months they are planning to crossadvertise six of their items by running interlocking television ads that mention both products.The following table shows Awesome’s estimate of the number of viewers (in
Engineers are designing a fixed route to be followed by automatic guided vehicles in a large manufacturing plant. The following table shows the east–west and north–south coordinates of the 6 stations to be served by vehicles moving continuously around the same route.1 2 3 4 5 6 E/W 20 40 180
An oil company currently has 5 platforms drilling off the Gulf coast of the United States.The following table shows the east–west and north–south coordinates of their shore base at point 0 and all the platform locations.0 1 2 3 4 5 E/W 80 10 60 30 85 15 N/S 95 15 70 10 75 30 Each day a
Every week Mighty Mo Manufacturing makes one production run of each of its 4 different kinds of metal cookware. Setup times to make any particular product vary depending on what was produced most recently. The following table shows the time (in hours) required to convert from any product to any
Every weekday afternoon, at the height of the rush hour, a bank messenger drives from the a bank’s central office to its 3 branches and returns with noncash records of the day’s activity.The following figure shows the freeway routes that are not hopelessly clogged by traffic at that hour and
Gotit Grocery Company is considering 3 locations for new distribution centers to serve it customers in 4 nearby cities. The following table shows the fixed cost (in millions of dollars) of opening each potential center, the number (in thousands) of truckloads forecasted to be demanded at each city
Basic Box Company is considering 5 new box designs of different sizes to package 4 upcoming lines of computer monitors. The following table shows the wasted space that each box would have if used to package each monitor.Missing values indicate a box that cannot be used for a particular monitor.Box
The figure that follows shows 5 pipelines under consideration by a natural gas company to move gas from its 2 fields to its 2 storage areas.The numbers on the arcs show the number of miles of line that would have to be constructed at$100,000 per mile.The figure also shows that storage facilities
Dandy Diesel manufacturing company assembles diesel engines for heavy construction equipment. Over the next 4 quarters the company expects to ship 40, 20, 60, and 15 units, respectively, but no more than 50 can be assembled in any quarter. There is a fixed cost of $2000 each time the line is setup
Top-T shirt company imprints T-shirts with cartoons and celebrity photographs. For each of their 4 pending contracts, the following table shows the number of days of production required, the earliest day the order can begin, and the day the order is due.1 2 3 4 Production 10 3 16 8 Earliest 0 20 1
Sarah is a graduate student who must make 4 large experimental runs on her personal computer as part of her thesis research. The jobs require virtually all the computer’s resources, so only one can be processed at a time and none can be interrupted once it has begun. The following table shows the
Three new jobs have just arrived at Fancy Finishing’s main furniture restoration shop. The following table shows the sequence that each must follow through the company’s 3 finish removal processes and the time required for each.Job Sequence Process Time 1 2 3 1 1–2–3 10 3 14 2 1–3–2 2 4
A team of auditors has divided itself into 3 groups, each to examine one category of records.Each group will review their speciality area for all 3 subsidiaries of the client being audited, but the required sequence and times differ, as shown in the following table.Subsidiary Sequence Group Time 1
With the addition of a new plant, Monsanto9 now has more capacity than it needs to manufacture its main chemical product. Numerous reactors i = 1,c, m can be operated at a variety j = 1,c, n of discrete combinations of settings for feed rate, reactor velocity, and reactor pressure. Both the
W.R. Grace10 strip mines phosphates in strata numbered from i = 1 at the top to i = n at the deepest level. Each stratum must be removed before the next can be mined, but only some of the layers contain enough suitable minerals to justify processing into the company’s three products: pebble,
Ault Food Limited11 is planning the production and distribution system for its new line of food products. Plants may be opened at any of sites i = 1,c, 7, and warehouses at locations j = 1,c, 13, to meet demands dk at customer regions k = 1,c, 219. Each plant costs $50 million to open and produces
Space structures12 designed for zero gravity have no structural weight to support and nothing to which a foundation can be attached.The structure needs only to withstand vibrations in space. This is accomplished by replacing truss members with dampers at a given number of p sites among j = 1,c, n
The National Cancer Institute13 has received proposals from 22 states to participate in its newest smoking intervention study. The first j = 1,c, 5 are from the Northeast region, the next j = 6,c, 11 from the Southeast, numbers j = 12,c, 17 from the Midwest, and the last j = 18,c, 22 from the West.
Every year the city of Montreal14 must remove large quantities of snow from sectors i = 1,c, 60 of the city. Each sector is assigned to one of sites j = 1,c, 20 as its primary disposal point. From prior-year history, planners have been able to estimate the expected volume of snowfall fi (in cubic
Highway maintenance in Australia15 is performed by crews operating out of maintenance depots. The Victoria region is planning a major realignments of its depots to provide more effective service to the i = 1,c, 276 highway segments in the region. A total of 14 sites must be selected from among the
Mobil Oil Corporation16 serves 600,000 customers with 430 tanktrucks operating out of 120 bulk terminals. As illustrated in the following figure, tanktrucks have several compartments c = 1,c, n of varying capacity uc.The final stage of distribution planning is to allocate outgoing gasoline products
Each of the 11 nurses17 at Rosey Retirement Home works a total of 10 days within each 2-week period, alternating between a compatible pair of weekly schedules taken from those depicted in the following table (1 = work, 0 = off).Day Shift 1 2 3 4 5 6 1 1 1 0 1 1 0 2 1 0 1 1 1 1 3 1 1 1 1 1 1 4 1 1 1
Regional Bell telephone operating companies, 18 which buy many products from a much smaller number of suppliers, often solicit discounts based on the total dollar volume of business awarded to particular suppliers. For example, suppliers i = 1,c, 25 might be required to quote base prices pi,j for
The small Adele19 textile company knits products p = 1,c, 79 on a variety of machines m = 1,c, 48 to meet known output quotas qp pounds for the next week. The variable cost per pound of making product p on machine m is known cm, p. Machines operate with changeable cylinder types j = 1,c, 14, which
Mail Order Mart (MOM)20 will ship qj pounds of small-order novelty goods over the next week to regions j = 1,c, 27 of the United States. MOM’s distribution facility is located in New England region 1. Orders can be directly shipped from the distribution center by small parcel carriers at cost p1,
Gas turbine engines21 have the following radial assembly of nozzle guides located immediately upstream from each rotor. The purpose of the vanes is to spread flow uniformly over the rotor, which improves its efficiency materially.During engine maintenance, the 55 old vanes are removed and replaced
A new freight airline22 is designing a huband-spoke system for its operations. From a total of 34 airports to be served, 3 will be selected as hubs. Then (one-way) airport-to-airport freight quantities fi,j will be routed via the hubs (fi,i = 0 for all i). That is, flow from i to j will begin at i,
In an area with many suburban communities, telephone listings are usually grouped into several different books.23 Patrons in each community i = 1,c, n are covered in exactly one directory k = 1,c, m. Numbers of patrons pi are known for each community, as well as (one-way) calling traffic levels
Solve each of the following discrete optimization models by total enumeration.(a) min 2x1 + x2 + 4x3 + 10x4 s.t. x1 + x2 + x3 … 2 3x1 + 7x2 + 19x3 + x4 Ú 20 x1, x2, x3 = 0 or 1 x4 Ú 0(b) max 30x1 + 12x2 + 24x3 + 55x4 s.t. 30x1 + 20x2 + 40x3 + 35x4 … 60 x2 + 2x3 + x4 Ú 2 x1 Ú 0 x2, x3, x4 =
Suppose that you have been asked to solve a mixed-integer ILP with 10,000 continuous and n binary decision variables. Determine the largest n’s for which the problem could be totally enumerated in one 24-hour day and in one 24-hour, 30-day month by each of the following computer environments.(a)
Consider the ILP max 14x1 + 2x2 - 11x3 + 17x4 s.t. 2x1 + x2 + 4x3 + 5x4 … 12 x1 - 3x2 - 3x3 - 3x4 … 0 x1 Ú 0 x2, x3, x4 = 0 or 1 Determine whether each of the following is a constraint relaxation.(a) max 14x1 + 2x2 - 11x3 + 17x4 s.t. 2x1 + x2 + 4x3 + 5x4 … 12 x1 - 3x2 - 3x3 - 3x4 … 0 xj Ú
Form the linear programming relaxation of each of the following ILPs.(a) min 12x1 + 45x2 + 67x3 + 1x4 s.t. 4x1 + 2x2 - x4 … 10 6x1 + 19x3 Ú 5 x2, x3, x4 Ú 0 x1 = 0 or 1 x3 integer(b) max 3x1 + 8x2 + 9x3 + 4x4 s.t. 2x1 + 2x2 + 2x3 + 3x4 … 20 29x1 + 14x2 + 78x3 + 20x4 … 100 x1, x2, x3 = 0 or
Each of the following ILPs has no feasible solutions. Solve the corresponding LP relaxation graphically and indicate whether your relaxation results are sufficient to show that the ILP is infeasible.(a) min 10x1 + 15x2 s.t. x1 + x2 Ú 2-2x1 + 2x2 Ú 1 x1, x2 = 0 or 1(b) max 40x1 + 17x2 s.t. 2x1 +
Determine the best bound on the optimal solution value of an ILP with each of the following objective functions that is available from the specified LP relaxation optima x .(a) max 24x1 + 13x2 + 3x3 x = a2, 12, 0b(b) min x1 - 6x2 + 49x3 x = a1, 0, 27 b(c) min 60x1 - 16x2 + 10x3 x = a12, 1, 12
Determine whether each of the following LP relaxation optima x is optimal in the corresponding ILP over the specified variable type constraints.(a) xj = 0 or 1, j = 1,c, 4 x = a1, 0, 13 , 23 b (b) x1, x2 = 0 or 1, x3, x4 Ú 0 x = a0, 1, 32 , 12 b (c) x1, x2, x3 = 0 or 1, x4 Ú 0 x = a1, 0, 1,
The ILP max 3x1 + 6x2 + 4x3 + 10x4 + 3x5 s.t. 2x1 + 4x2 + x3 + 3x4 + 7x5 … 10 x1 + x3 + x4 … 2 4x2 + 4x4 + 4x5 … 7 x1,c, x5 = 0 or 1 has LP relaxation optimal solution x =10, 0.75, 1, 1, 02.(a) Determine the best bound on the ILP optimal solution value available from relaxation results.(b)
Do Exercise 12-8 for the ILP min 12x1 + 5x2 + 4x3 + 6x4 + 7x5 s.t. 6x1 + 8x2 + 21x3 + 6x4 + 5x5 Ú 11 x1 + x2 + 2x3 + x4 Ú 1 2x2 + 5x3 + x5 Ú 2 x1,c, x5 = 0 or 1 and LP relaxation optimum x = 10, 0, 0.524, 0, 02.
Do Exercise 12-8 for the ILP min 17x1 + 12x2 + 24x3 + 2x4 + 8x5 s.t. 3x1 + 5x3 + 7x4 + 9x5 Ú 13 7x2 + 4x4 + 11x5 Ú 5 2x1 + 3x2 + 2x3 + 3x4 Ú 7 x2, x3, x4 = 0 or 1 x1, x5 Ú 0 and LP relaxation optimum x = 10.5, 1, 0, 1, 0.52.
Do Exercise 12-8 for the ILP min 50x1 + 25x2 + 100x3 + 300x4+ 200x5 + 500x6 s.t. 10x1 + 6x2 + 2x3 = 45 2x1 + 3x2 + x3 Ú 12 0 … x1 … 5x4 0 … x2 … 5x5 0 … x3 … 5x6 x4, x5, x6 = 0 or 1 and LP relaxation optimum x = 11.5, 5, 0, 0.3, 1, 02.
Consider the ILP min 10x1 + 20x2 + 40x3 + 80x4 - 144y s.t. x1 + x2 + x3 + x4 Ú 4y x1,c, x4, y = 0 or 1(a) Solve the full ILP model by inspection.(b) Verify by inspection that its LP relaxation has optimal solution x = 11, 1, 0, 02, y = 12.(c) Show that an equivalent ILP would result if the main
Do Exercise 12-12 for ILP min 16x1 + 14x2 + 15x3 s.t. x1 + x2 Ú 1 x2 + x3 Ú 1 x1 + x3 Ú 1 x1,c, x3 = 0 or 1 LP relaxation optimum x = 112, 12, 12 2 and revised main constraint x1 + x2 + x3 Ú 2
Consider the Fixed Charge Network Flow instance displayed below (see Section 11.6).Numbers on arcs are fixed charges fij. All variable costs cij = 0.(a) Formulate the instance as in 11.31 using decision variables xij ! flow on arc (i, j), and yij = 1 if xi, j 7 0 and = 0 otherwise.(b) Identify by
The fixed-charge ILP min 60x1 + 78x2 + 200y1 + 400y2 s.t. 12x1 + 20x2 Ú 64 15x1 + 10x2 … 60 x1 + x2 … 10 0 … x1 … 100y1 0 … x2 … 100y2 y1, y2 = 0 or 1 has LP relaxation optimum x = 10, 3.22, y = 10, 0.0322.(a) Compute the smallest replacements for big-M values of 100 in this
Do Exercise 12-15 for the averagecompletion-time, single-machine scheduling ILP min 0.51x1 + 12 + x2 + 82 s.t. x1 + 12 … x2 + 7511 - y2 x2 + 8 … x1 + 75y x1, x2 Ú 0 y = 0 or 1 with LP relaxation optimum x = 10, 02, y = 0.08.[Hint: Consider the sum of the process times in part (a).]
Suppose that an integer linear program has decision variables x1, x2, x3 = 0 or 1. List all completions of the following partial solutions.(a) (#, 0, #)(b) (1, 0, #)
The following is the complete branch and bound tree for an ILP over decision variables x1,c, x4 = 0 or 1.(a) List the partial solutions associated with each node of the tree.(b) Which nodes were branched and which terminated?(c) Identify the nodes of the tree that have x = 10, 1, 0, 12 as a
Do Exercise 12-18 for the branch and bound tree x=1 0 x4=0 1 2 x2=1 x2=0 4 3
Suppose that the ILP of Exercise 12-8 is being solved by branch and bound. State the candidate problem associated with each of the following partial solutions.(a) (#, 1, #, #, 0)(b) (#, 1, 0, 1, #)
Suppose that a minimizing ILP is being solved by LP-based branch and bound Algorithm 12A over decision variables x1, x2, x3 = 0 or 1, x4 Ú 0. Show how the search should process the node with x2 = 1 and other variables free if the corresponding LP relaxation has each of the following outcomes.
The following table shows the LP relaxation outcomes for all possible combinations of fixed and free variables in branch and bound solution of a minimizing integer linear program over decision variables x1, x2, x3 = 0 or 1, x4 Ú 0. Solve the problem by LP-based Algorithm 12A and record your
Do Exercise 12-22 for a minimizing mixedinteger linear program over binary variables w1, w2, w3, and w4 Ú 0. W1 W2 10'3 LP Optimum LP Value ######### # # 0 # # # 0 # 0 0 1 1 1 0 # 0 # 0 # 0 0 0 0 0 0 0 1 # 0 1 0 1 1 # 1 # 1 # 1 0 10 10 1 1 1 1 1 1 +01+01+01+01+01+01+01+01+01 # (0.2, 0.0, 0.0, 0.0)
Consider a maximizing MILP over x1 Ú 0, and x2, x3, x4 = 0 or 1.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record your computations in a branch and bound tree. When more than one node is active, select the deepest in
Consider a minimizing MILP over x1, x2, x3 binary and x4 Ú 0.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record your computations in a branch and bound tree. When more than one node is active, apply the Depth-First
Consider a maximizing mixed-integer liner program with x1 Ú 0, x2, x3, x4 = 0 or 1.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record your computations in a branch and bound tree. When more than one node is active,
Students often mistakenly believe ILPs are more tractable than LPs because the straightforward rules of Algorithm 12A seem less complex than the simplex and interior point methods of Chapters 5–7.(a) Explain why solution of any ILP by LPbased branch and bound always takes at least as much work as
In most applications, LP based Branch and Bound Algorithm 12A actually investigates only a tiny fraction of the possible partial solutions.Still, this is not always the case. Consider the family of ILPs of the form min y s.t. 2a nj = 1 xj + y = n xj = 0 or 1 j = 1,c, n y = 0 or 1 where n is odd.(a)
The branch and bound tree Figure 12.10 records solution of the knapsack model min 90x1 + 50x2 + 54x3 s.t. 60x1 + 110x2 + 150x3 Ú 50 x1, x2, x3 = 0 or 1 by LP-based Algorithm 12A under rules of Exercise 12-22.Briefly describe the processing, including how and why nodes were branched or terminated,
Do Exercise 12-29 for max 51x1 + 72x2 + 41x3 s.t. 17x1 + 10x2 + 14x3 … 19 x1, x2, x3 = 0 or 1 and tree in Figure 12.11figurE 12.10 Branch and Bound Tree for Exercise 12-29 x3=1 6)(0,0,1) 54 0 (0, 0, 0.33) 12=1 18 x3=0 5)(0,1,0) 50 1 (0, 0.45,0) 22.7 12=0 2)(0.83, 0, 0) x=1 75 x=0 3 4 infeasible
Return to the knapsack problem of Exercise 12-29.(a) Explain why LP relaxation optimal solutions can be rounded to integer-feasible solutions by setting xn jd
Do Exercise 12-31 on the knapsack model of Exercise 12-30, this time rounding solutions xn jd :x j;.
For each of the following branch and bound trees determine the best lower and upper bounds on the value of an optimal solution known from parent bounds and incumbent solutions after processing of each node. Also show the maximum percent error that would have resulted if processing had terminated
The branch and bound tree that follows shows the incomplete solution of a maximizing ILPby LP-based Algorithm 12A, with numbers next to nodes indicating LP relaxation solution values.Node 4 has just produced the first incumbent solution, and nodes a to d remain unexplored.(a) Show which unexplored
The branch and bound tree that follows shows the incomplete solution of a minimizing ILP by LP-based Algorithm 12A, with numbers next to nodes indicating LP relaxation solution values.Node 4 has just produced the first incumbent solution, and nodes a to d remain unexplored.(a) Show which unexplored
Repeat Exercise 12-22, following the same rules except:(a) Use the best-first enumeration sequence and allow termination by parent bounds.(b) Use the depth-forward best-back enumeration sequence and allow termination by parent bounds.
Do Exercise 12-36 for the branch and bound of Exercise 12-26.
Three company trucks must be assigned to pickup 7 miscellaneous loads on the way back from their regular deliveries. Truck capacities and load sizes (cubic yards) are shown in the following table, together with the extra distance (in miles) that each truck would have to travel if it is to deviate
Return to the ILP of Exercise 12-12 with LP relaxation optimum x = 11, 1, 0, 02, y = 12.Determine whether each of the following is a valid inequality for the ILP, and if so, whether it would strengthen the original LP relaxation to add the inequality as a constraint.(a) x2 + x3 + x4 Ú 3y(b) x1
Return to the ILP of Exercise 12-13 with LP relaxation optimum x = 112, 12, 1 22. Determine whether each of the inequality for the ILP, and if so, whether it would strengthen the original LP relaxation to add the inequality as a constraint.(a) 10x1 + 10x2 + 10x3 Ú 25(b) x1 + x2 + x3 Ú 1(c) x1 +
The ILP max 40x1 + 5x2 + 60x3 + 8x4 s.t. 18x1 + 3x2 + 20x3 + 5x4 … 25 x1,c, x4 = 0 or 1 has LP relaxation optimum x = 1 5 18, 0, 1, 02. Determine whether each of the following is a valid inequality for the ILP, and if so, whether it would strengthen the LP relaxation to add the inequality as a
The following tree records solution of a maximizing ILP over x1, x2, x3 = 0 or 1 by branch and cut Algorithm 12B. LP relaxations solutions show next to each node.Briefly describe the processing, including how and why nodes were branched tightened or terminated, when incumbent solutions were
Do Exercise 12-42 for the following tree of a minimizing ILP over x1, x2, x3 = 0 or 1. (0) (0.2, 0, 0.6) 50 x2+2x32 1) (0.2, 0.5, 0.75) 57 x=1 3 (1,0,1) 63 solve 2) (0.6, 0.4, 1) 58 x=0 4 (0, 1, 0.5) 61 3x2+3x35 5) (0, 1, 0.67) 65
The tree below shows the evolution of a hypothetical Branch and Cut Algorithm 12B solution of a given minimizing, all-binary ILP.Relaxation solutions are shown next to nodes, and both fixed variables and new cuts are indicated on the branches.Take nodes in sequence, one by one, and briefly describe
The LP relaxation of a standard form ILP over constraints Ax =b, x Ú 0, x integer, with 3 rows and 7 variables, has been solved for basic variables x1, x2, and x5 to obtain the dictionary form (see Section 5.4).RHS x3 x4 x6 x7 x1 = 1.6 -2.7 1.1 -2.3 13.4 x2 = 3.0 = 3.9 -4.7 2.8 2.2 x3 = 2.4 0.6
Consider the binary knapsack polytope 18x1 + 3x2 + 20x3 + 17x4 + 6x5+ 10x6 + 5x7 + 12x8 … 25 x1,c, x8 = 0 or 1(a) Identify 5 minimal cover inequalities valid for this knapsack polytope, including the one involvin the last 3 variables, and briefly justify why each meets the requirements of
Air National Guard planners are loading a cargo plane with crates of supplies and equipment needed to help victims of the recent wave of floods in the Northeast. The table below shows the criticality of the need for each crate, its weight(in tons), and its volume (in hundreds of cubic feet). The
Consider the binary ILP max 21x1 + 21x2 + 48x3 + 33x4 + 18x5+ 17x6 + 39x7 s.t. 5x1 + 14x2 + 12x3 + 21x4 + 1x5+ 6x6 + 13x7 … 30 [i]x1 + x2 + x3 … 1 [ii]xj binary for all j [iii](a) Use class optimization software to solve both the full ILP and its LP relaxation.(b) Explain why minimum cover
The plot below depicts the solution space of pure binarary ILP min 3x1 + 4x2 s.t. 4x1 + 2x2 Ú 1 5x1 + 10x2 Ú 4 x1, x2 = 0 or 1Coordinates and solution values of important points are pre-computed in the key.(a) Sketch the convex hull of integer solutions on the plot and briefly justify your
Consider a pure-integer program over constraints-1x1 + 2x2 … 4 5x1 + 1x2 … 20-2x1 - 2x2 … -7 x1, x2 Ú 0 and integer(a) Draw a 2-dimensional plot of the LPrelaxation feasible set.(b) Identify all integer-feasible solutions and their convex hull.(c) Determine the dimension of this convex
Return to the ILP of Exercises 12-13 and 12-40.(a) Draw a 3-dimensional sketch of the convex hull of feasible solutions to this model(b) Determine the dimension of the convex hull.(c) For each of (a)–(d) in Exercise 12-40 yielding a valid inequality, determine (by showing the required number of
The following plot shows the feasible space for an ILP over nonnegative integer variables x1 and x2.(a) Identify the convex hull of integer-feasible solutions.(b) Determine the dimension of the convex hull and confirm your answer with a suitable number of affinely independent points.(c) Derive the
Consider solving an ILP of the following form by Delayed Column Generation Algorithm 13A.min aj cj xj s.t. aj ai, j xj Ú bi i = 1,c, 5 all xj Ú 0 and integer where right-hand sides are given positive integers, bi … 5, coefficients ai, j in any column j are nonnegative integers summing to at
Emergency relief agency ERNow is planning flights of small helicopters to deliver medical, food, and housing supplies for populations cutoff by a recent hurricane. The following table shows the fraction of each plane’s weight wi and volume vi capacity of shipping containers for different
The Silo State IE faculty is dividing its 12 members into 4 teams of 3 to develop ideas for a long-term strategic plan. Like all faculties, the professors are not all equally compatible with each other. The table below provides a compatibility score (0 bad to 100 good) for each possible pair.(a)
The tree below shows the hypothetical evolution of a Branch and Price Algorithm 13B solution of an all-binary ILP in original variables x1, x2, and x3. Relaxation solutions are shown next to nodes, and both fixed variables and new columns (variables) are identified on the branches.(a) Is the model
Do Exercise 13-4 for the Branch-and-Price below on an all-binary ILP over original variables x1, x2, x3 and x4. (no initial incumbent) x=1 add x5 add x (0, 1/2, 1, 2/3) 40 (1, 1, 0, 1, 2/3) 35 2)(0, 1/2, 1, 1, 1, 1/4) 33 4(0,1,1,0,1,1/3,0) 39 add xg 2=0 3 (0, 0, 1, 1, 1, 1) 42 4 add x 5 (0, 1, 1,
Consider the ILP max 30x1 + 55x2 + 20x3 s .t. 40x1 - 12x2 + 11x3 … 55 19x1 + 60x2 + 3x3 Ú 20 3x1 + 2x2 + 2x3 = 5 x1, x2, x3 = 0 or 1 Form the Lagrangian relaxations obtained by dualizing each of the following collections of main constraints, and show all sign restrictions that apply to Lagrange
Consider the facilities location ILP min 3x1,1 + 6x1,2 + 5x2,1 + 2x2,2+250y1 + 300y2 s .t . 30x1,1 + 20x1,2 … 30y1 30x2,1 + 20x2,2 … 50y2 x1,1 + x2,1 = 1 x1,2 + x2,2 = 1 0 … x1,1, x1,2, x2,1, x2,2 … 1 y1 = 0 or 1(a) Use total enumeration to compute all optimal solution.(b) Form a Lagrangian
Add to Exercise 13-7(a)-(f) the following:(g) Compute the subgradient direction of Algorithm 13C at your solution of (f)and take a step using lambda = 500 to update the dual solution. Then re-solve the Lagrangian relaxation. Did the value improve?(h) Repeat (g) by taking a second step from the
Do Exercise 13-7 for the generalized assignment model min 15x1,1 + 10x1,2 + 30x2,1 + 20x2,2 s .t. x1,1 + x1, 2 = 1 x2,1 + x2,2 = 1 30x1,1 + 50x2,1 … 80 30x1,2 + 50x2,2 … 60 x1,1, x1,2, x2,1, x2,2 = 0 or 1 Dualize the first two main constraints and solve with v = 10, 02, v = 110, 122, and v =
Consider the binary integer program min 5x1 - 2x2 s .t. 7x1 - x2 Ú 5 x1, x2 binary(a) Formulate and justify a Lagrangian relaxation dualizing the only main constraint with multiplier v.(b) Briefly explain why your relaxation of (a)is indeed a relaxation of the full ILP model.(c) Comment on whether
Consider the following binary ILP:max 13x1 + 22x2 + 18x3 + 17x4 + 11x5 + 19x6 + 25x7 s.t. a 7j = 1xj … 3 3x1 + 7x2 + 5x3 … 15 12x4 + 9x5 + 8x6 + 6x7 … 11 xj binary, j = 1,c, 7(a) State the corresponding Lagrangian relaxation dualizing only the first main constraint, and initializing its dual
Consider the tiny LP constraint set-w1 + w2 … 1 w1 + 2w2 Ú 1 w1, ww Ú 0(a) Sketch the feasible set of these constraints in a 2-dimensional plot.(b) Establish that the feasible set is convex.(c) List all the extreme points of the set.(d) List all the extreme directions.(e) Show that each of the
Consider solving the following 4-variable LP by Dantzig-Wolfe Decomposition Algorithm 13D. Constraints 1 and 2 will constitute the linking problem, numbers 3-5 the first subproblem, and numbers 6-8 the second.(a) Sketch the feasible set of the constraints for the first subproblem in a 2-dimensional
Do Exercise 13-13 on the following LP starting with extreme points 1x1, x22 = 10, 02 and 1x3, x42 = 136, 02 in part (e). min 200x1 +350x2 +450x3 +220x4 s.1. 2x1 + 1x2 + 4x3 + 3x4 100 5x1 + 5x2 + 9x3 + 7x4 177 +x1 5 +5x +4x2 32 20 +1x3 +4x4 36 +1x4 4 X3 X40
Consider solving the following MILP by Benders Decomposition Algorithm 13E. Treat the y variables as the complicating ones, and begin with y102 = 10, 02.max 60x1 + 50x2 - 25y1 - 100y2 s.t. 20x1 + 17x2 - 60y1 - 30y2 … 10 11x1 + 13x2 - 30y1 - 60y2 … 10 x1, x2 Ú 0;y1, y2 [0, 10] and integer(a)
Consider solving the the following minimum total cost facilities location model with Benders Decomposition Algorithm 13E, taking numbers on supply nodes as the fixed cost and capacity (if opened), those on demand nodes as the required inflow, and numbers on arcs as unit costs of transportation.(a)
Consider the following Binary Knapsack Problem (BKP) instance max 7x1 + 9x2 + 21x3 + 15x4 s.t. 8x1 + 4x2 + 12x3 + 7x4 … 19 1BKP2 x1,c, x4 = 0 or 1(a) Construct the corresponding Dynamic Programming digraph (like Figure 9.16), including showing objective function coefficients on all arcs
Return to the (BKP) of Exercise 14-l.(a) Define a finite alphabet of symbols, and then show a binary encoding of that instance in terms of your alphabet.(b) Establish that your encoding of (a) has length proportional to the number of variables n, and the logarithms (rounded up) of objective
is an instance of the Binary Knapsack Problem (BKP) form max a nj = 1cjxj s.t. a nj = 1ajxj … b x1,c, xn = 0 or 1(d) The Dynamic Programming algorithm of 14-1 solves instances of (BKP) by computing a longest path in a network across n stages with at most b states each. Explain why those

Showing 2900 - 3000 of 4739

First
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Last

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved