Second Engineering Optimization Day
March 31, 2010


 


The Second Engineering Optimization Day aims to bring together researchers, students, and industry experts to discuss the latest trends in using Optimization in real-life settings. The one-day event aims to provide an opportunity to exchange ideas and share experience in applying optimization to engineering and industry problems.

Plenary Speakers

Prof. Bernard Gendron
Department of Computer Science and Operations Research, University of Montréal

Prof. John Mitchell
Department of Mathematical Sciences, Rensselaer Polytechnic Institute

Industry Speakers from

Frito-Lay
Bombardier
Navtech

Organizing Committee

Samir Elhedhli (Chair)
Associate Professor, Department of Management Sciences, University of Waterloo
Phone: (519) 888-4567-x35683, Email: elhedhli-at-uwaterloo.ca

Joe Naoum-Sawaya
Ph.D. Candidate, Department of Management Sciences, University of Waterloo
Phone: (519) 888-4567-x32359, Email: jnaoumsa-at-uwaterloo.ca

Bissan Ghaddar
Ph.D. Candidate, Department of Management Sciences, University of Waterloo
Phone: (519) 888-4567-x32359, Email: bghaddar-at-uwaterloo.ca

Time and Location
The Second Engineering Optimization day will take place in Laurel Room, South Campus Hall at the University of Waterloo on Wednesday, March 31, 2010 (8.30am-5.00pm)

Registration
The registration deadline is March 22, 2010. Please complete the online registration form. There is no registration fee.

Transportation and Parking
The University of Waterloo, located at 200 University Avenue West, Waterloo, N2L 3G1 is easily accessible by car, Greyhound bus, and train. For driving directions, please visit mapquest.com. Visitor parking are available in UW place behind the Woolwich Court (located through the intersection of University Avenue West and Phillip Street - see I- 4.5 of the campus map).

Sponsors
- Canadian Operational Research Society
- University of Waterloo Student Chapter of the Canadian Operational Research Society
- Faculty of Engineering, University of Waterloo
- Department of Management Sciences, University of Waterloo

Schedule

8:30-9:00
Opening Remarks by the Dean of Engineering Adel Sedra
Continental Breakfast
9:00-10:00
Plenary Talk
John Mitchell (Rensselaer Polytechnic Institute)
Linear Programs with Complementarity Constraints: Algorithms and Applications
10:00-10:25
Elizabeth Jewkes (University of Waterloo)
Performance Analysis and Optimization of Hybrid Manufacturing Systems under a Batch Ordering Policy
10:25-10:50
Industry Talk

Frito-Lay
Ron Clark, Director, Go to Market, Frito Lay Canada.
Route Engineering / Logistics for Frito Lay
10:50-11:05
Coffee Break
11:05-11:30
Juan Vera (University of Waterloo)
Static Arbitrage Bounds for European Option Prices on baskets
11:30-11:55
Samir Elhedhli (University of Waterloo)
Column Generation for Large Scale Scheduling Problems
11:55-12:20
Ricardo Fukasawa (University of Waterloo)
On the Solution of the Time-Dependent Traveling Salesman Problem
12:20-13:30
Lunch Break
13:30-14:30
Plenary Talk
Bernard Gendron (University of Montréal)
Reformulations and Decomposition for Multicommodity Capacitated Network Design
14:30-14:55
Fatma Gzara (University of Waterloo)
Network Design for Hazardous Material Transportation
14:55-15:20
Catherine P. Rosenberg (University of Waterloo)
Joint Routing and Medium Access Control in Wireless Networks: An Optimization Approach
15:20-15:45
Industry Talk

Bombardier
Richard Chong, Methods Engineer, Production Analysis.
Peter Schnurr, Methods Engineering Specialist, Production Analysis.
Vanessa Guha.
Optimizing Aerospace Manufacturing (Bombardier Aerospace)
15:45-16:00
Coffee Break
16:00-16:25
Industry Talk

Navtech
Robert Gerbracht
Mike Yeo, Vice President, Technology.
Robert Mora, Product Director.
Airline Crew Scheduling
16:25-16:50
Ada Barlatt (University of Waterloo)
Using Composite Variable Modeling to Achieve Realism and Tractability in Production Planning: An Example from Automotive Stamping

Abstracts

Linear Programs with Complementarity Constraints: Algorithms and Applications

JOHN E. MITCHELL

Department of Mathematical Sciences, Rensselaer Polytechnic Institute

Linear programs with complementarity constraints (LPCCs) have many applications in practice. Perhaps the best known are formulations of bilevel linear programming problems and of nonconvex quadratic programming problems. We discuss other applications, including inverse convex quadratic programming, cross-validated support vector regression, quantile minimization, and testing copositivity of matrices on polyhedral cones.

We also describe two algorithms for LPCCs. The first is a logical Benders decomposition method, where the subproblem is a linear program and the master problem is a satisfiability problem. The second method is a branch-and-cut algorithm, which exploits disjunctive cuts and cuts arising from the structure of the LPCC.

(Joint work with Jong-Shi Pang.)


Performance Analysis and Optimization of Hybrid Manufacturing Systems under a Batch Ordering Policy

ELIZABETH JEWKES

Department of Management Sciences, University of Waterloo

We consider a two-stage hybrid manufacturing system for a single product where the intermediate components are Made-To-Stock (MTS) and then differentiated when the demand is realized through a Make-To-Order (MTO) stage. Inventory for intermediate components is held between the two stages. We introduce a batch ordering policy to account for economies of scale in ordering due to a cost associated with each order placed. We use the Matrix-geometric method to evaluate system performance under this ordering policy. Afterwards, we develop an optimization model to find the optimal intermediate buffer size and the optimal replenishment order quantity for the system. We show that a base stock policy is sub-optimal in the presence of a replenishment cost for common components. The savings from adopting the batch ordering policy can be high while the response time for most customer orders is not affected.

(Joint work with Eman Almehdawe.)


Route Engineering / Logistics for Frito Lay

RON CLARK

Director, Go to Market, Frito Lay Canada

We have about 1500 sales routes across Canada serving our customers in various channels (Grocery, Mass Merch, Convenience, Gas, Drug, etc). We have different route types depending on geography and customer mix. We discuss how we determine the various route types, challenges we face as an organization and our specific tools to perform and opitmize our route engineering.


Column Generation for Large Scale Scheduling Problems

SAMIR ELHEDHLI

Management Sciences, University of Waterloo

We consider a basic problem in timetabling and scheduling that we model as a bin packing problem with conflicts. We propose a column generation approach based on 0/1 knapsack subproblems with conflicts and a branching rule that matches the conflict constraints.
First, the solution of the master problems is initialized using columns generated from classical knapsack problems, and are filtered to satisfy the conflicting constraints. Second, the solution of child nodes exploits most of the information at parent nodes. Third, maximum clique inequalities are generated for the subproblems. Finally, the memory is well managed by proper storage and access to generated columns. The algorithm is tested on a standard set of problems. Numerical results indicate it efficiency in solving large instances within reasonable computational time.


On the solution of the Time-Dependent Traveling Salesman Problem.

RICARDO FUKASAWA

Combinatorics & Optimization, University of Waterloo

The time-dependent traveling salesman problem is a generalization of the classic traveling salesman problem where costs depend on the position of the arc in the route. We present new valid inequalities for that problem that are derived from an extended formulation by Picard and Queyranne. These inequalities, when combined with a Dantzig-Wolfe formulation provide very good dual bounds, often solving the problem at the root node. We show some facet-defining conditions for some of the inequalities as well as separation results. Computational results are presented comparing our approach to other previous works on the same problem.

(Joint work with Hernan Abeledo, Artur Pessoa and Eduardo Uchoa.)


Reformulations and Decomposition for Multicommodity Capacitated Network Design

BERNARD GENDRON

Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)
Département d’informatique et de recherche opérationnelle, Université de Montréal

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. Motivated by these reformulations, we develop a general algorithmic scheme, which we call Structured Dantzig-Wolfe (SDW) decomposition that can be used for solving large-scale structured Linear Programs (LPs). The required structure of the LPs is the same as in the original Dantzig-Wolfe (DW) approach, that is, a polyhedron over which optimization is “easy” plus a set of “complicating" constraints. Under the hypothesis that an alternative model for the “easy” polyhedron and a simple map between the formulations are available, we propose a finite procedure which solves the original LP. The original DW decomposition method is easily seen to be a special case of the new procedure corresponding to the standard choice for the model of the “easy” polyhedron where there is a variable for each of its extreme points and rays. Furthermore, some techniques developed for the standard DW decomposition can be easily adapted to the new approach, giving rise to Stabilized Structured Dantzig-Wolfe (SSDW) decomposition methods that can be more efficient than their non-stabilized brethren. We compare several decomposition algorithms to compute the same lower bound on the optimal value of the multicommodity capacitated network design problem: 1) a cutting-plane algorithm based on the generation of residual capacity inequalities within the model with general integer variables; 2) a standard DW approach; 3) a stabilized DW (or bundle) method; 4) an SDW algorithm solved by simultaneous variable and constraint generation; 5) an SSDW approach. The latter is shown to generally outperform the other methods on a large class of randomly generated instances.

(Joint work with Antonio Frangioni, Dipartimento di Informatica, Universita di Pisa, Polo Universitario della Spezia.)


Network Design for Hazardous Material Transportation

FATMA GZARA

Management Sciences, University of Waterloo

We consider the network design problem for hazardous material transportation that is modeled as a bilevel multi-commodity network flow model. In addition to being difficult to solve, the model is known to be ill-posed. We study the formulation and present results on the solution space. We show that a network is not bilevel feasible only if it has cycles that satisfy certain conditions. We propose a family of valid cuts to eliminate such infeasible solutions and incorporate them within an exact cutting plane algorithm. Numerical results show the efficiency of the proposed cutting plane algorithm in terms of computational time and solution quality. It solves large scale problems in significantly smaller CPU time and finds optimal solutions that are of similar or better quality than other models and solution methods in the literature.


Joint Routing and Medium Access Control in Wireless Networks: An Optimization Approach

CATHERINE ROSENBERG

Electrical and Computer Engineering, University of Waterloo

Wireless mesh networks (WMNs) are seen as a promising alternative to other (wired) broadband access technologies. In order to offer high throughput, they will have to be correctly configured by the operator in terms of routing, scheduling, power control, and rate adaptation. We present here the joint routing and MAC problem formulation, a description of the very powerful computational tool that we have developed to solve it and some of the new engineering insights that we could obtained thanks to the tool.


Optimizing Aerospace Manufacturing (Bombardier Aerospace)

RICHARD CHONG, PETER SCHNURR, and VANESSA GUHA

BOMBARDIER

Direct labour accounts for 10-13%* of commercial aircraft costs and commercial aircraft operating margins are between 5-8%*. Consequently, a 10% improvement in labour productivity increases operating margins by 20-25%. Utilization, process methods and individual performance must be improved to see gains in labour productivity. The number of variables involved in aircraft manufacturing can be overwhelming to a manager, and without proper organization/clarity of the statement of work in a work center, the manager’s ability to balance, optimize and problem solve can be hindered, resulting in poor overall labour productivity. The approach taken to tackle these issues (workstream project) is to create manageable work packages and clearly define the critical path at first, and create a work/operator utilization optimization tool later.


Airline Crew Scheduling

ROBERT GERBRACHT, MIKE YEO, and ROBERT MORA

NAVTECH

Airline crew scheduling has been an active and fruitful research topic since the mid 60s. Due to the combinatorial nature of the problem, literally dozens of aircrew optimization programs were either built or bought by the airline industry in the next decade or so, with none of them successful. Starting in the early 70s the introduction of Set Partitioning approaches began to produce useful results. As increased computer power and algorithm advances became available the programs matured and became able to accommodate more realistic aspects of the scheduling problem (daily, weekly, monthly scheduling periods, soft constraints, artificial costs to trade off operational robustness and crew quality-of-life factors against out-of-pocket costs, etc.). The last decade has seen a proliferation of nominally global optimizers claiming to obtain the true mathematical global optimum solution.
The fact is that none of the global optimizers achieve a true global minimum cost solution. Since the crew scheduling problem is an NP-hard problem, the standard approach now uses column generation techniques to generate one or a small sequence of reasonably sized subsets (106-107 of the 1015-1020 possible crew routings (aka pairings)) that will allow a reduction in cost from an incumbent solution. The heart of the column generation approach to building candidate crew pairings is a shortest distance or shortest time algorithm that links multiple candidate duty periods into a domicile-to-domicile round trip crew routing. By replacing the distance measure with the cost of the duty period this becomes a lowest cost algorithm. This approach was initially designed for long-haul fleets where the time away from base largely determined the cost of a routing minimizing the time also minimized the overall costs.
This basic approach is now being applied to both short-haul and long-haul fleets, and either application runs into similar problems. The shortest distance algorithm is ill-suited to accommodate constraints that apply to the pairing as a whole or across multiple duty periods, rather than to individual duty periods. Examples are a maximum flight time limit within a 7-day period, or a minimum flight time limit for the pairing as a whole. The shortest distance algorithm ignores such constraints. When a shortest distance candidate pairing is constructed it has to be tested against these constraints. If it violates one of them there is no easy way to determine which one(s) of the duty periods should be replaced to satisfy the limit (a pairing is typically comprised of up to 3-5 duties for a short-haul problem, up to 10-12 for a long-haul problem). Back tracking the tree of included duty periods is necessary, but at present there seems to be no fast and efficient method for doing so. As a result the column generation phase of the process slows down considerably and the leading global optimizers ignore as many of this type of constraint as they possibly can. The result is often solutions that look good on paper but which are far from optimum in the larger real world optimization arena in which airlines must operate.
We require a fast and efficient means of generating good candidate pairings that satisfy multiple overall pairing constraints. Imagine, for example, that you are given or can build the complete set of all possible duty periods beginning from every station, all satisfying all duty period-specific constraints and accurately priced. There will be tens of thousands of possible duties, perhaps even as many as a million In the column generation approach the individual flight legs comprising any duty period will reflect the reduced costs found from the previous (now incumbent) solution. To improve the incumbent solution we now need to build the best set of candidate pairings that use these duty periods (and satisfy rules for the minimum rest time between them), storing the pairings with an overall negative cost when the leg reduced costs are factored in. The key requirement is that such pairings must satisfy a variety of constraints over several or all of the duty periods in the pairing.



Static Arbitrage Bounds for European Option Prices on baskets

JUAN VERA

Department of Management Sciences, University of Waterloo

An European Option gives the buyer the right, but not the obligation, to buy or to sell a particular asset on a fixed future date (maturity time), at an agreed price (strike price). The price of the option depends on the distribution of the asset price at maturity. We will present a linear programming (LP) based model to compute bounds on the price of a European option on a basket given the prices of European options on the underlying assets. This is done without assuming any particular type of future price distribution.
We will survey the general moment problem and then we will concentrate on the moment problem over piece-wise linear functions; we will show how to solve this problem using LP-methods. The European option pricing is obtained then as an application of our method. We will also discuss some other applications in finance and insurance.

(Joint work with Javier Peña, Xavier Saynac and Luis Zuluaga.)


Using Composite Variable Modeling to Achieve Realism and Tractability in Production Planning: An Example from Automotive Stamping

ADA BARLATT

Department of Management Sciences, University of Waterloo

Applying traditional mathematical programming techniques to problems in production planning can lead to tremendous challenges. These include non-linearities, very large numbers of constraints, and weak linear programming relaxations. To ensure tractability, problems are often either simplified in scope or limited in instance size, resulting in solutions that may no longer address important real-world issues. As an alternative, we consider the use of models based on composite variables (variables that capture multiple decisions simultaneously) as a way to solve complex production planning problems. We use the problem of scheduling an automotive stamping facility as a demonstrative example, showing how composite variable models and a novel corresponding algorithm can lead to high-quality, realistic solutions with acceptable run times. In our approach, we do not restrict batch sizes, labor availability, or sequencing of part types; nor do we fix the number of changeovers a priori. In addition, we allow sequence-dependent changeover times and varying due dates. Computational results are presented using data from Ford Motor Company.

(Joint work with Amy Cohn, Yakov Fradkin, Oleg Gusikhin, and Craig Morford.)