Top

Symmetry, Integer Linear Programming, Complete Enumeration and Design of Experiments

Workshop on Symmetry in Integer Linear Programming, Enumeration Algorithms and Design of Experiments

Leuven, 22 March 2018

A common problem in optimization is the existence of symmetry or isomorphism. To limit the computing time for optimization problems involving symmetry or isomorphic solutions, it is crucial to implement some form of symmetry breaking. In this workshop, Professor Jeff Linderoth from the University of Wisconsin at Madison will deliver a lecture on symmetric integer problems. His lecture will be followed by two presentations on problems in design of experiments, where symmetry is an issue as well. In his talk on optimizing blocking arrangements for orthogonal arrays, Professor Peter Goos (KU Leuven) will demonstrate that different problem formulations are one way to deal with symmetry. Professor Eric Schoen will present an algorithm to enumerate non-isomorphic orthogonal arrays. The final presentation of the day will be delivered by doctoral candidate José Núnez Ares (KU Leuven), who will discuss integer programming approaches to finding trend-robust run orders of experimental designs and to enumerating minimally aliased response surface (MARS) designs. The theme that is common is all the talks is symmetry.

Programme and abstracts

13h00-14h30: Solving Symmetric Integer Programs (Prof. J. Linderoth)

We will discuss two mechanisms for dealing with integer programs that contain a great deal of symmetry: orbital branching and isomorphism pruning. These methods use information encoded in the symmetry group of the integer program to guide the branching decision and prune nodes of the search tree. Orbital branching and isomorphism pruning will be compared, and we will introduce an extension that demonstrates how to combine the two.

We will finish by describing how isomorphism pruning was combined with a variety of enumerative techniques to attempt to tackle the “football pool problem”, a famous open problem in coding theory which asks the cardinality of the smallest covering code of the space {0,1,2}^6. With our approach, lower bounds on the size of an optimal code have been improved from 65 to 71. Sharpening this bound has required decades of CPU time on a computational grid consisting of thousands of non-dedicated CPUs.

The talk is based on joint work with James Ostrowski, Fabrizio Rossi, Stefano Smriglio, Francois Margot, and Greg Thain.

14h50-15h40: Symmetry Breaking Formulations for Blocking Orthogonal Experimental Designs (Prof. P. Goos)

Two-level orthogonal designs play an important role in industrial screening experiments, in which the primary goal is to identify the treatment factors with the largest main effects on the output of a process or the performance of a product. Often, the experimental tests suggested by the orthogonal designs cannot be performed on a single day or using a single batch of raw material. This causes day-to-day or batch-to-batch variation in the experimental results, and necessitates the use of orthogonal blocking patterns. These blocking patterns ensure that the factors’ main effects can be estimated independently from the day-to-day or batch-to-batch variation. Finding an optimal orthogonal blocking pattern for an orthogonal design is a major challenge. Recently, mixed integer linear programming has been used for that purpose. While this approach is promising, computational experiments have indicated it is quite slow. We show how to speed up the mixed integer linear programming approach by adding symmetry breaking constraints to the formulation, and study the usefulness of an asymmetric representatives formulation. In other words, we introduce state-of-the-art symmetry breaking approaches in optimal experimental design. We perform extensive computational experiments to test which combinations of symmetry breaking constraints work best. Throughout, we consider two kinds of symmetry: symmetry due to the fact that the blocks can be relabeled without affecting the quality of the blocking pattern, and symmetry due to replicated test combinations. We also study the impact of various symmetry breaking options available in the solvers, and we compare the performance of CPLEX and Gurobi. (Reference: Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs by Nha Vo-Thanh, Raf Jans, Eric D. Schoen, and Peter Goos, Cahiers du GERAD G-2016-117)

15h40-16h30:Symmetry reduction by constraint programming: the case of orthogonal array enumeration (Prof. E. Schoen)

Researchers often desire experimental designs which require small numbers of tests. Designs based on orthogonal arrays are particularly popular, because the experimental results from such designs can partly be analyzed by comparing mean values for subsets of the tests. Examples of orthogonal arrays are Taguchi arrays, Plackett-Burman designs and designs based on Hadamard matrices. Each array involves a certain number of tests, N, a certain number of factors to investigate, n, and a certain number of factor settings, s. The property that makes an array orthogonal is that, for any pair of factors, all s2 combinations of factor settings occur equally often. It turns out that there may exist many different orthogonal arrays for a given combination of N, n and s. Relabeling the order of the tests, the order of the factors and the settings of each factor results in an array with the same statistical properties. Arrays that can be obtained from each other using these operations are therefore considered isomorphic, but there can also be many non-isomorphic arrays for a given combination of N, n and s. An important research area in experimental design is therefore to enumerate non-isomorphic orthogonal arrays and identify which ones are the most useful for practical experimentation. A particular challenge is to deal with the symmetry in the enumeration problem, caused by the fact that permutations of the rows, the columns and the factor settings produce isomorphic arrays. In this talk, we present an enumeration approach based on constraint programming, the definition of a canonical form and a fast test to check whether an array is of that form. The algorithm we developed can handle scenarios in which all factors have the same number of settings, but also scenarios in which factors can have different numbers of settings. We generated an extensive catalogue of complete series of non-isomorphic arrays and identified those that are most useful for practitioners. To date, the catalogue is, most likely, the most extensive one in the world.

17h00-19h00: Trend-Robust and Minimally Aliased Response Surface Designs by means of Integer Programming (Public Ph.D. defense, José Núnez Ares)

Gaining competitive advantage requires today’s businesses to innovate at an increasing speed. New product development is at the heart of innovation and requires substantial experimentation. The field of “design of experiments” delivers a systematic plan to determine the settings that lead to the optimal product. In this PhD thesis, we have focused on Response Surface Designs (RSDs), a core component of the response surface methodology, which is widely used in industry. Our work addresses two gaps in the existing literature on RSDs. The first problem we tackled is concerned with a multi-factor experiment carried out over a period of time and in which the responses depend on a time trend. Unless the tests of the experiment are conducted in a proper order, the time trend has a negative impact on the precision of the estimates of the main effects, the interaction effects and the quadratic effects. In the literature, most of the methods used to construct proper orders are tailored to specific designs, and are not applicable to an arbitrary design. We developed a sequential approach based on integer programming to find a trend-robust run order for any given design, which succeeds in identifying trend-robust run orders for arbitrary RSDs with two up to six factors. Our second topic’s motivation lies in the fact that good RSDs tend to be expensive. By means of a tailored integer programming framework with advanced symmetry reduction techniques, we were able to deploy an enumeration algorithm on the Open Science Grid, a vast computing grid infrastructure in USA. This algorithm allowed us to build an extensive database of novel cost-efficient designs with attractive statistical properties. In addition, we have developed a first version of a software prototype that intuitively guides a practitioner toward the most suitable design for a broad class of applications.

Practicalities

University of Leuven - Maria Theresiacollege, Sint-Michielsstraat 6, 3000 Leuven - MTC3 00.15 (which is in the Augustinus part of the building)

The venue is in the historical town center of Leuven. Information about how to reach the venue can be found here.

Travel information

Leuven is easy to reach by train from the Brussels train stations (roughly 20-30 minutes), from Liège (30 minutes) and from the Brussels national airport (15 minutes by train). Note that the Brussels South airport is further.

Speakers

mkdf-team-image

Jeffrey T. Linderoth

A full professor at the University of Wisconsin-Madison, Professor Linderoth focuses on solving large-scale numerical optimization problems. Specific areas on which has has worked include Mixed-Integer Linear Programming, Mixed-Integer Nonlinear Programming, Stochastic Programming, Grid Computing, and High Performance Computing.<br />

mkdf-team-image

Peter Goos

A full professor at the Faculty of Bio-Science Engineering of the University of Leuven and at the Faculty of Applied Economics of the University of Antwerp, where he teaches various introductory and advanced courses on statistics and probability. His main research area is the statistical design and analysis of experiments.

mkdf-team-image

Eric Schoen

A guest professor at the Faculty of Bio-Science Engineering of the University of Leuven, Eric Schoen has performed a tremendous amount of work on the enumeration, exploration and classification of orthogonal arrays.

mkdf-team-image

José Núnez Ares

A Ph.D. candidate at the Faculty of Bioscience Engineering of the KU Leuven, José Núnez Ares has used integer programming techniques for tackling several problems in design of experiments. He built a large catalog of minimally aliased response surface or MARS designs.