Monique Guignard-Spielberg

Antonio Alonso-Ayuso, Laureano F. Escudero, Monique Guignard-Spielberg, Martin Quinteros, Andres Weintraub (Forthcoming), Forestry management under uncertainty, Annals of Operations Research.

Antonio Alonso-Ayuso, Laureano Escudero, Monique Guignard-Spielberg, 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.

Artur Alves Pessoa, Peter M. Hahn, Monique Guignard-Spielberg, Yi-Rong Zhu (2010), Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique, European Journal of Operational Research, October 2010, vol. 206, issue 1, 54-63. 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 well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization 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.

Peter M. Hahn, Yi-Rong Zhu, Monique Guignard-Spielberg, J. MacGregor Smith (2010), Exact solution of emerging quadratic assignment problems, International Transactions in Operational Research, September 2010, Volume 17, Issue 5, 525-552.

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 Guignard-Spielberg, Alexander Meeraus, Fred O'Brien (2010), Term-End Exam Scheduling at United States Military Academy/West Point, Journal of Scheduling, (2010) 13: 375–391.

Abstract: Scheduling term-end 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 conflict-free 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 technically-trained. 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, Bum-Jin Kim, Monique Guignard-Spielberg, J. MacGregor Smith, Yi-Rong Zhu (2008), An Algorithm for the Generalized Quadratic Assignment Problem, Computational Optimization and Applications, July 2008, Vol. 40, Iss. 3, 351-372.

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 pair-wise 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, Bum-Jin Kim, Thomas Stützle, Sebastian Kanthak, William L. Hightower, Harvind Samra, Zhi Ding, Monique Guignard-Spielberg (2008), The quadratic three-dimensional assignment problem: Exact and approximate solution methods, European Journal of Operational Research, Volume 184, Issue 2, 16 January 2008, Pages 416-428.

Abstract: This paper reports on algorithm development for solving the quadratic three-dimensional 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 re-transmissions, 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 Guignard-Spielberg (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 Guignard-Spielberg (Working), The Convex Hull Relaxation for Nonlinear Interger Programs With Linear Constraints.

Warren P. Adams, Monique Guignard-Spielberg, Peter M. Hahn, William L. Hightower (2007), A Level-2 Reformulation-Linearization Technique Bound for the Quadratic Assignment Problem, European Journal of Operational Research, Volume 180, Issue 3, 1 August 2007, Pages 983-996. 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 level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal 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