Monique Guignard Spielberg

Antonio AlonsoAyuso, Laureano F. Escudero, Monique GuignardSpielberg, Martin Quinteros, Andres Weintraub (Forthcoming), Forestry management under uncertainty , Annals of Operations Research.

Artur Alves Pessoa, Peter M. Hahn, Monique GuignardSpielberg, YiRong Zhu (2010), Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the ReformulationLinearization Technique, European Journal of Operational Research, October 2010, vol. 206, issue 1, 5463. 10.1016/j.ejor.2010.02.006

Abstract: In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the wellknown quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branchandbound scheme with a new Lagrangean relaxation procedure over a known RLT (ReformulationLinearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.

Antonio AlonsoAyuso, Laureano Escudero, Monique GuignardSpielberg, Martin Quinteros, Andres Weintraub (2010), Uncertainty in forest production planning , Wiley Encyclopedia of Operations Research and Management Science, Ed. by James J. Cochran, 2010, Wiley and Sons, Inc.

Peter M. Hahn, YiRong Zhu, Monique GuignardSpielberg, J. MacGregor Smith (2010), Exact solution of emerging quadratic assignment problems, International Transactions in Operational Research, September 2010, Volume 17, Issue 5, 525552.

Abstract: We report on a growing class of assignment problems that are increasingly of interest and very challenging in terms of the difficulty they pose to attempts at exact solution. These problems address economic issues in the location and design of factories, hospitals, depots, transportation hubs and military bases. Others involve improvements in communication network design. In this article we survey the latest and best methods available for solving exactly these difficult problems and suggest a taxonomy that provides a framework for combining existing solution methods and sets of computer tools that can be modified and extended to make inroads in solving this growing class of optimization problems.

Siqun Wang, Michael Bussieck, Monique GuignardSpielberg, Alexander Meeraus, Fred O'Brien (2010), TermEnd Exam Scheduling at United States Military Academy/West Point, Journal of Scheduling, (2010) 13: 375–391.

Abstract: Scheduling termend exams (TEE) at the United States Military Academy in West Point is unlike any other exam timetabling problem we know of. Exam timetabling normally produces a conflictfree timetable covering a reasonably long exam period, where every exam is scheduled exactly once for all the students enrolled in the corresponding class. The situation is quite different at West Point. There are hundreds of exams to schedule over such a short time period that there is simply no feasible solution. The challenge is then to allow something that is not even considered elsewhere, that is, creating multiple sessions of some exams, scheduled at different times within the exam period, to allow each student to take all exams he/she must take. The overall objective is to find a feasible exam schedule with a minimum number of such duplicate exams. The paper describes a system that has been developed at GAMS Development Corp. in close cooperation with the scheduling staff at West Point, and that has been used successfully since 2001. It uses mathematical optimization in several modules, and some of the techniques proposed are new. It is fast and flexible, and allows for human interaction, such as adding initially unexpected constraints, coming for instance from instructors’ preferences and dislikes, as well as their hierarchical rankings. It is robust and can be used by people familiar with the organization at West Point, without the need for them to be technicallytrained. Overall, using the course and student information databases, it is an effective decision support system that calls optimization tools in an unobtrusive way.

Peter M. Hahn, BumJin Kim, Monique GuignardSpielberg, J. MacGregor Smith, YiRong Zhu (2008), An Algorithm for the Generalized Quadratic Assignment Problem, Computational Optimization and Applications, July 2008, Vol. 40, Iss. 3, 351372.

Abstract: This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pairwise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15.

Peter M. Hahn, BumJin Kim, Thomas Stützle, Sebastian Kanthak, William L. Hightower, Harvind Samra, Zhi Ding, Monique GuignardSpielberg (2008), The quadratic threedimensional assignment problem: Exact and approximate solution methods, European Journal of Operational Research, Volume 184, Issue 2, 16 January 2008, Pages 416428.

Abstract: This paper reports on algorithm development for solving the quadratic threedimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet retransmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64. We present an exact solution method based upon a reformulation linearization technique that is one of the best available for solving the quadratic assignment problem (QAP). Our current exact algorithm is useful for Q3AP instances of size 13 or smaller. We also investigate four stochastic local search algorithms that provide optimum or near optimum solutions for large and difficult QAP instances and adapt them for solving the Q3AP. The results of our experiments make it possible to get good solutions to signal mapping problems of size 8 and 16.

Monique GuignardSpielberg (Working), A New, Solvable, Primal Relaxation for Nonlinear Integer Programming Problems with Linear Constraints.

Abstract: This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a linearization method (see for instance Gunn and Rai 12). It can be solved iteratively by a sequence of linear integer programming problems and nonlinear problems over a simplex. The relaxation should be designed so that the linear integer programming problems are relatively easy to solve. These subproblems yield Lagrangean?like integer solutions that can be used as starting points for Lagrangean heuristics. We also describe a primal decomposition, similar in spirit to Lagrangean decomposition, for problems with several structured subsets of constraints. A small example is solved explicitly in each case by an extension of the linearization method of Frank and Wolfe 7, similar in spirit to Simplicial Decomposition (von Hohenbalken, 17). The primal relaxation was introduced in Guignard 9, and described briefly in Guignard [10]. Improved solution methods are studied in Contesse and Guignard 5 and 6, and successful implementations are described in 1, 2, 3 and [4]. This paper by contrast concentrates on the concept of primal relaxation and its properties. In the linear case, the primal relaxation is equivalent to Lagrangean relaxation.

Aykut Ahlatcioglu and Monique GuignardSpielberg (Working), The Convex Hull Relaxation for Nonlinear Interger Programs With Linear Constraints.

Warren P. Adams, Monique GuignardSpielberg, Peter M. Hahn, William L. Hightower (2007), A Level2 ReformulationLinearization Technique Bound for the Quadratic Assignment Problem, European Journal of Operational Research, Volume 180, Issue 3, 1 August 2007, Pages 983996. 10.1016/j.ejor.2006.03.051

Abstract: This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0–1 linear representations that result from a reformulation–linearization technique (rlt). The rlt provides different “levels” of representations that give increasing strength. Prior studies have shown that even the weakest level1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level2. We compare level2 with level1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level1 by implementing a Lagrangian relaxation that exploits blockdiagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances

Past Courses

OIDD910 CONCEPTS OF MATH PROGRAM

Introduction to mathematical programming for PhD students who would like to be intelligent and sophisticated consumers of mathematical programming theory but do not plan to specialize in this area. Integer and nonlinear programming are covered, including the fundamentals of each area together with a sense of the stateoftheart and expected directions of future progress.

OIDD916 ADVANCED INTEGER PROGRMG

Indepth review of solution methods: Lagrangean relaxation and column generation, Benders partitioning, crossdecomposition, surrogate relaxation, cutting planes and valid inequalities, logical processing, probing, branchandbound, branchandprice. Study of special problems and applications: matching, location, generalized assignment, traveling salesman, forest planning, production scheduling.

Received the 2008 Computational Optimization And Applications Best Paper Award, 2008 Description

“An Algorithm for the Generalized Quadratic Assignment Problem,” Peter M. Hahn, BumJin Kim, Monique Guignard, J. MacGregor Smith and YiRong Zhu, Computational Optimization and Applications,  July 2008, Vol. 40, Iss. 3, 351372.

Received first prize at SOBRAPO Meeting in Brazil, 2008 Description

“Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the ReformulationLinearization Technique,”  Artur Alves Pessoa, Peter M. Hahn, Monique Guignard and YiRong Zhu. European Journal of Operational Research, October 2010, vol. 206, issue 1, 5463.

Invited to attend the XII Combinatorial Optimization Meeting in, 2007