Publications
126 results found
Letsios D, Baltean-Lugojan R, Ceccon F, et al., 2020, Approximation algorithms for process systems engineering, COMPUTERS & CHEMICAL ENGINEERING, Vol: 132, ISSN: 0098-1354
- Author Web Link
- Cite
- Citations: 2
Thebelt A, Kronqvist J, Lee RM, et al., 2020, Global Optimization with Ensemble Machine Learning Models, Editors: Pierucci, Manenti, Bozzano, Manca, Publisher: ELSEVIER SCIENCE BV, Pages: 1981-1986
- Author Web Link
- Cite
- Citations: 4
Sedgwick R, Goertz J, Stevens M, et al., 2020, Design of Experiments for Verifying Biomolecular Networks
Botoeva E, Kouvaros P, Kronqvist J, et al., 2020, Efficient Verification of ReLU-Based Neural Networks via Dependency Analysis, 34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence, Publisher: ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, Pages: 3291-3299, ISSN: 2159-5399
- Author Web Link
- Cite
- Citations: 37
Wiebe J, Cecílio I, Misener R, 2019, Data-driven optimization of processes with degrading equipment, Industrial & Engineering Chemistry Research, Vol: 57, Pages: 17177-17191, ISSN: 0888-5885
In chemical and manufacturing processes, unit failures due to equipment degradation can lead to process downtime and significant costs. In this context, finding an optimal maintenance strategy to ensure good unit health while avoiding excessive expensive maintenance activities is highly relevant. We propose a practical approach for the integrated optimization of production and maintenance capable of incorporating uncertain sensor data regarding equipment degradation. To this end, we integrate data-driven stochastic degradation models from Condition-based Maintenance into a process level mixed-integer optimization problem using Robust Optimization. We reduce computational expense by utilizing both analytical and data-based approximations and optimize the Robust optimization parameters using Bayesian Optimization. We apply our framework to five instances of the State-Task-Network and demonstrate that it can efficiently compromise between equipment availability and cost of maintenance.
Letsios D, Bradley JT, Suraj G, et al., 2019, Approximating bounded job start scheduling with application in Royal Mail deliveries under uncertainty, Publisher: arXiv
Motivated by mail delivery scheduling problems arising in Royal Mail, westudy a generalization of the fundamental makespan scheduling P||Cmax problemwhich we call the "bounded job start scheduling problem". Given a set of jobs,each specified by an integer processing time p_j, that have to be executednon-preemptively by a set of m parallel identical machines, the objective is tocompute a minimum makespan schedule subject to an upper bound g<=m on thenumber of jobs that may simultaneously begin per unit of time. We show thatLongest Processing Time First (LPT) algorithm is tightly 2-approximate. Afterproving that the problem is strongly NP-hard even when g=1, we elaborate onimproving the 2-approximation ratio for this case. We distinguish the classesof long and short instances satisfying p_j>=m and p_j<m, respectively, for eachjob j. We show that LPT is 5/3-approximate for the former and optimal for thelatter. Then, we explore the idea of scheduling long jobs in parallel withshort jobs to obtain tightly satisfied packing and bounded job startconstraints. For a broad family of instances excluding degenerate instanceswith many very long jobs, we derive a 1.985-approximation ratio. For generalinstances, we require machine augmentation to obtain better than 2-approximateschedules. Finally, we exploit machine augmentation and lexicographicoptimization, which is useful for P||Cmax under uncertainty, to propose atwo-stage robust optimization approach for bounded job start scheduling underuncertainty aiming in good trade-offs in terms of makespan and number of usedmachines. We substantiate this approach numerically using Royal Mail data.
Kouyialis G, Wang X, Misener R, 2019, Symmetry Detection for Quadratic Optimization Using Binary Layered Graphs, PROCESSES, Vol: 7
- Author Web Link
- Cite
- Citations: 1
Campos JS, Misener R, Parpas P, 2019, A multilevel analysis of the Lasserre hierarchy, European Journal of Operational Research, Vol: 277, Pages: 32-41, ISSN: 0377-2217
This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. For these cases, and assuming that the lower order semidefinite programming relaxation has been solved, we develop prolongation operators that exploit the solutions already calculated to find initial approximations for the solution of the higher order relaxation. We can prove feasibility in the higher order of the hierarchy of the points obtained using the operators, as well as convergence to the optimal as the relaxation order increases. Furthermore, the operators are simple and inexpensive for problems where the projection over the feasible set is “easy” to calculate (for example integer {0, 1} and {−1,1} POPs). Our numerical experiments show that it is possible to extract useful information for real applications using the prolongation operators. In particular, we illustrate how the operators can be used to increase the efficiency of an infeasible interior point method by using them as an initial point. We use this technique to solve quadratic integer {0, 1} problems, as well as MAX-CUT and integer partition problems.
Wiebe J, Cecílio I, Misener R, 2019, Robust optimization for the pooling problem, Industrial & Engineering Chemistry Research, Vol: 58, Pages: 12712-12722, ISSN: 0888-5885
The pooling problem has applications, e.g., in petrochemical refining, water networks, and supply chains and is widely studied in global optimization. To date, it has largely been treated deterministically, neglecting the influence of parametric uncertainty. This paper applies two robust optimization approaches, reformulation and cutting planes, to the non-linear, non-convex pooling problem. Most applications of robust optimization have been either convex or mixed-integer linear problems. We explore the suitability of robust optimization in the context of global optimization problems which are concave in the uncertain parameters by considering the pooling problem with uncertain inlet concentrations. We compare the computational efficiency of reformulation and cutting plane approaches for three commonly-used uncertainty set geometries on 14 pooling problem instances and demonstrate how accounting for uncertainty changes the optimal solution.
Čyras K, Letsios D, Misener R, et al., 2019, Argumentation for explainable scheduling, Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), Publisher: AAAI, Pages: 2752-2759
Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of 'what-if' scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones.
Olofsson S, Misener R, 2019, GPdoemd: a python package for design of experiments for model discrimination, Computers & Chemical Engineering
GPdoemd is an open-source python package for design of experiments for model discrimination that uses Gaussian process surrogate models to approximate and maximise the divergence between marginal predictive distributions of rival mechanistic models. GPdoemd uses the divergence prediction to suggest a maximally informative next experiment.
Furini F, Traversi E, Belotti P, et al., 2019, QPLIB: a library of quadratic programming instances, Mathematical Programming Computation, Vol: 11, Pages: 237-265, ISSN: 1867-2949
This paper describes a new instance library for quadratic programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function and/or the constraints are quadratic. QP is a very diverse class of problems, comprising sub-classes ranging from trivial to undecidable. This diversity is reflected in the variety of QP solution methods, ranging from entirely combinatorial approaches to completely continuous algorithms, including many methods for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the different, interested communities is therefore important. We propose a simple taxonomy for QP instances leading to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.
Olofsson SCW, Mehrian M, Calandra R, et al., 2019, Bayesian multi-objective optimisation with mixed analytical and black-box functions: application to tissue engineering, IEEE Transactions on Biomedical Engineering, Vol: 66, Pages: 727-739, ISSN: 0018-9294
Tissue engineering and regenerative medicine looks at improving or restoring biological tissue function in humans and animals. We consider optimising neotissue growth in a three-dimensional scaffold during dynamic perfusion bioreactor culture, in the context of bone tissue engineering. The goal is to choose design variables that optimise two conflicting objectives: (i) maximising neotissue growth and (ii) minimising operating cost. We make novel extensions to Bayesian multi-objective optimisation in the case of one analytical objective function and one black-box, i.e. simulation-based, objective function. The analytical objective represents operating cost while the black-box neotissue growth objective comes from simulating a system of partial differential equations. The resulting multi-objective optimisation method determines the trade-off in the variables between neotissue growth and operating cost. Our method outperforms the most common approach in literature, genetic algorithms, in terms of data efficiency, on both the tissue engineering example and standard test functions. The resulting method is highly applicable to real-world problems combining black-box models with easy-to-quantify objectives like cost.
Ceccon F, Siirola J, Misener R, 2019, SUSPECT: MINLP special structure detector for pyomo, Optimization Letters, Vol: 14, Pages: 801-814, ISSN: 1862-4472
We present SUSPECT, an open source toolkit that symbolically analyzesmixed-integer nonlinear optimization problems formulated using the Python alge-braic modeling library Pyomo. We present the data structures and algorithms used toimplement SUSPECT. SUSPECT works on a directed acyclic graph representation ofthe optimization problem to perform: bounds tightening, bound propagation, mono-tonicity detection, and convexity detection. We show how the tree-walking rules inSUSPECT balance the need for lightweight computation with effective special struc-ture detection. SUSPECT can be used as a standalone tool or as a Python library to beintegrated in other tools or solvers. We highlight the easy extensibility of SUSPECTwith several recent convexity detection tricks from the literature. We also report ex-perimental results on the MINLPLib 2 dataset.
Wiebe J, Cecilio I, Misener R, 2019, The robust pooling problem, Editors: Kiss, Zondervan, Lakerveld, Ozkan, Publisher: ELSEVIER SCIENCE BV, Pages: 907-912, ISBN: 978-0-12-819939-8
Letsios D, Kouyialis G, Misener R, 2018, Reprint of: Heuristics with performance guarantees for the minimum number of matches problem in heat recovery network design, Computers and Chemical Engineering, Vol: 116, Pages: 422-450, ISSN: 1873-4375
Heat exchanger network synthesis exploits excess heat by integrating process hot and cold streams and improves energy efficiency by reducing utility usage. Determining provably good solutions to the minimum number of matches is a bottleneck of designing a heat recovery network using the sequential method. This subproblem is an -hard mixed-integer linear program exhibiting combinatorial explosion in the possible hot and cold stream configurations. We explore this challenging optimization problem from a graph theoretic perspective and correlate it with other special optimization problems such as cost flow network and packing problems. In the case of a single temperature interval, we develop a new optimization formulation without problematic big-M parameters. We develop heuristic methods with performance guarantees using three approaches: (i) relaxation rounding, (ii) water filling, and (iii) greedy packing. Numerical results from a collection of 51 instances substantiate the strength of the methods.
Baltean-Lugojan, Misener R, 2018, Piecewise parametric structure in the pooling problem - from sparse, strongly-polynomial solutions to NP-hardness, Journal of Global Optimization, Vol: 71, Pages: 655-690, ISSN: 0925-5001
The standard pooling problem is a NP-hard subclass of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity, focusing on the single quality standard pooling problem in its p-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems are rooted in piecewise-defined functions. We introduce dominant active topologies under relaxed flow availability to explicitly identify pooling problem sparsity and show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the paper explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the P / NP boundary. We formally present the results obtained and their derivations for various specialized single quality pooling problem subclasses.
Misener R, Allenby, Fuentes-Gari M, et al., 2018, Stem Cell Biomanufacturing under Uncertainty: A Case Study in Optimizing Red Blood Cell Production, AIChE Journal, Vol: 64, Pages: 3011-3022, ISSN: 0001-1541
As breakthrough cellular therapy discoveries are translated into reliable, commercializable applications, effective stem cell biomanufacturing requires systematically developing and optimizing bioprocess design and operation. This manuscript proposes a rigorous computational framework for stem cell biomanufacturing under uncertainty. Our mathematical tool kit incorporates: high-fidelity modeling; single- and multivariate sensitivity analysis; global topological superstructure optimization; robust optimization. We quantitatively demonstrate the advantages of the proposed bioprocess optimization framework using, as a case study, a dual hollow fiber bioreactor producing red blood cells from progenitor cells. The optimization phase reduces the cost by a factor of 4 and the price of insuring process performance against uncertainty is approximately 15% over the nominal optimal solution. Mathematical modeling and optimization can guide decision making; we quantitatively evaluate the possible commercial impact of this cellular therapy using the disruptive technology paradigm.
Olofsson S, Deisenroth M, Misener R, 2018, Design of experiments for model discrimination hybridising analytical and data-driven approaches, 35th International Conference on Machine Learning (ICML), Publisher: ICML
Healthcare companies must submit pharmaceuti-cal drugs or medical devices to regulatory bodiesbefore marketing new technology. Regulatorybodies frequently require transparent and inter-pretable computational modelling to justify a newhealthcare technology, but researchers may haveseveral competing models for a biological sys-tem and too little data to discriminate betweenthe models. In design of experiments for modeldiscrimination, the goal is to design maximallyinformative physical experiments in order to dis-criminate between rival predictive models. Priorwork has focused either on analytical approaches,which cannot manage all functions, or on data-driven approaches, which may have computa-tional difficulties or lack interpretable marginalpredictive distributions. We develop a method-ology introducing Gaussian process surrogatesin lieu of the original mechanistic models. Wethereby extend existing design and model discrim-ination methods developed for analytical modelsto cases of non-analytical models in a computa-tionally efficient manner.
Olofsson S, Deisenroth MP, Misener R, 2018, Design of Experiments for Model Discrimination using Gaussian Process Surrogate Models, Computer Aided Chemical Engineering, Vol: 44, Pages: 847-852, ISSN: 1570-7946
© 2018 Elsevier B.V. Given rival mathematical models and an initial experimental data set, optimal design of experiments for model discrimination discards inaccurate models. Model discrimination is fundamentally about finding out how systems work. Not knowing how a particular system works, or having several rivalling models to predict the behaviour of the system, makes controlling and optimising the system more difficult. The most common way to perform model discrimination is by maximising the pairwise squared difference between model predictions, weighted by measurement noise and model uncertainty resulting from uncertainty in the fitted model parameters. The model uncertainty for analytical model functions is computed using gradient information. We develop a novel method where we replace the black-box models with Gaussian process surrogate models. Using the surrogate models, we are able to approximately marginalise out the model parameters, yielding the model uncertainty. Results show the surrogate model method working for model discrimination for classical test instances.
Letsios D, Misener R, 2018, Exact lexicographic scheduling and approximate rescheduling
In industrial scheduling, an initial planning phase may solve the nominalproblem and a subsequent recovery phase may intervene to repair inefficienciesand infeasibilities, e.g. due to machine failures and job processing timevariations. This work investigates the minimum makespan scheduling problem withjob and machine perturbations and shows that the recovery problem is stronglyNP-hard, at least as hard as solving the problem with full input knowledge. Weexplore recovery strategies with respect to the (i) planning decisions and (ii)permitted deviations from the original schedule. The resulting performanceguarantees are parameterized by the degree of uncertainty. The analysis derivesfrom the optimal substructure imposed by lexicographic optimality, solexicographic optimization enables more efficient reoptimization. We revisitstate-of-the-art exact lexicographic optimization methods and propose a novellexicographic optimization approach based on branch-and-bound. Numericalanalysis using standard commercial solvers substantiates the method.
Mistry M, Callia D'Iddio A, Huth MRA, et al., 2018, Satisfiability modulo theories for process systems engineering, Computers and Chemical Engineering, Vol: 113, Pages: 98-114, ISSN: 1873-4375
Process systems engineers have long recognized the importance of both logic and optimization for automated decision-making. But modern challenges in process systems engineering could strongly benefit from methodological contributions in computer science. In particular, we propose satisfiability modulo theories (SMT) for process systems engineering applications. We motivate SMT using a series of test beds and show the applicability of SMT algorithms and implementations on (i) two-dimensional bin packing, (ii) model explainers, and (iii) MINLP solvers.
Letsios D, Kouyialis G, Misener R, 2018, Heuristics with performance guarantees for the minimum number of matches problem in heat recovery network design, Computers and Chemical Engineering, Vol: 113, Pages: 57-85, ISSN: 1873-4375
Heat exchanger network synthesis exploits excess heat by integrating process hot and cold streams and improves energy efficiency by reducing utility usage. Determining provably good solutions to the minimum number of matches is a bottleneck of designing a heat recovery network using the sequential method. This subproblem is an NPNP-hard mixed-integer linear program exhibiting combinatorial explosion in the possible hot and cold stream configurations. We explore this challenging optimization problem from a graph theoretic perspective and correlate it with other special optimization problems such as cost flow network and packing problems. In the case of a single temperature interval, we develop a new optimization formulation without problematic big-M parameters. We develop heuristic methods with performance guarantees using three approaches: (i) relaxation rounding, (ii) water filling, and (iii) greedy packing. Numerical results from a collection of 51 instances substantiate the strength of the methods.
Letsios D, Kouyialis G, Misener R, 2018, Heuristics with performance guarantees for the minimum number of matches problem in heat recovery network design, Publisher: arXiv
Heat exchanger network synthesis exploits excess heat by integrating process hot and cold streams and improves energy efficiency by reducing utility usage. Determining provably good solutions to the minimum number of matches is a bottleneck of designing a heat recovery network using the sequential method. This subproblem is an NP-hard mixed-integer linear program exhibiting combinatorial explosion in the possible hot and cold stream configurations. We explore this challenging optimization problem from a graph theoretic perspective and correlate it with other special optimization problems such as cost flow network and packing problems. In the case of a single temperature interval, we develop a new optimization formulation without problematic big-M parameters. We develop heuristic methods with performance guarantees using three approaches: (i) relaxation rounding, (ii) water filling, and (iii) greedy packing. Numerical results from a collection of 51 instances substantiate the strength of the methods.
Mistry M, Letsios D, Krennrich G, et al., 2018, Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded, Publisher: INFORMS
- Author Web Link
- Open Access Link
- Cite
- Citations: 13
Mehrian M, Guyot Y, Papantoniou I, et al., 2018, Maximizing neotissue growth kinetics in a perfusion bioreactor: An in silico strategy using model reduction and Bayesian optimization, Biotechnology and Bioengineering, Vol: 115, Pages: 617-629, ISSN: 0006-3592
In regenerative medicine, computer models describing bioreactor processes can assist in designing optimal process conditions leading to robust and economically viable products. In this study, we started from a (3D) mechanistic model describing the growth of neotissue, comprised of cells, and extracellular matrix, in a perfusion bioreactor set‐up influenced by the scaffold geometry, flow‐induced shear stress, and a number of metabolic factors. Subsequently, we applied model reduction by reformulating the problem from a set of partial differential equations into a set of ordinary differential equations. Comparing the reduced model results to the mechanistic model results and to dedicated experimental results assesses the reduction step quality. The obtained homogenized model is 105 fold faster than the 3D version, allowing the application of rigorous optimization techniques. Bayesian optimization was applied to find the medium refreshment regime in terms of frequency and percentage of medium replaced that would maximize neotissue growth kinetics during 21 days of culture. The simulation results indicated that maximum neotissue growth will occur for a high frequency and medium replacement percentage, a finding that is corroborated by reports in the literature. This study demonstrates an in silico strategy for bioprocess optimization paying particular attention to the reduction of the associated computational cost.
Olofsson S, Deisenroth MP, Misener R, 2018, Design of experiments for model discrimination hybridising analytical and data-driven approaches, Pages: 6259-6269
Healthcare companies must submit pharmaceutical drugs or medical devices to regulatory bodies before marketing new technology. Regulatory bodies frequently require transparent and interpretable computational modelling to justify a new healthcare technology, but researchers may have several competing models for a biological system and too little data to discriminate between the models. In design of experiments for model discrimination, the goal is to design maximally informative physical experiments in order to discriminate between rival predictive models. Prior work has focused either on analytical approaches, which cannot manage all functions, or on datadriven approaches, which may have computational difficulties or lack interpretable marginal predictive distributions. We develop a methodology introducing Gaussian process surrogates in lieu of the original mechanistic models. We thereby extend existing design and model discrimination methods developed for analytical models to cases of non-analytical models in a computationally efficient manner.
Wesselhoeft C, Ham DA, Misener R, 2018, Algorithms for Mixed-Integer Optimization Constrained by Partial Differential Equations, Computer Aided Chemical Engineering, Pages: 799-804
Mixed-integer, partial differential equation (PDE) constrained optimization (MIP-DECO) is a flexible modeling framework with many engineering applications, e.g. tidal and wind turbine siting, pharmaceutical business operations, disaster recovery, and solid product creation. But solving MIPDECO is daunting because it combines both integer programming and partial differential equations in a single optimization model. We consider a range of optimization algorithms for addressing MIPDECO from two applications: (i) the Source Inversion and (ii) the Tidal Stream Turbine Optimization problems. We report on the relevant merits of these approaches and make our results available as an open source extension to OpenTidalFarm.
Letsios D, Kouyialis G, Misener R, 2018, Approximation Algorithms for Process Systems Engineering, Editors: Friedl, Klemes, Radl, Varbanov, Wallek, Publisher: ELSEVIER SCIENCE BV, Pages: 565-566
Kouyialis G, Misener R, 2017, Symmetry Detection for Quadratically Constrained Quadratic Programs Using Binary Layered Graphs
Symmetry in mathematical programming may lead to a multiplicity of solutions.In nonconvex optimisation, it can negatively affect the performance of thebranch-and-bound algorithm. Symmetry may induce large search trees withmultiple equivalent solutions, i.e. with the same optimal value. Dealing withsymmetry requires detecting and classifying it first. This work developsmethods for detecting groups of symmetry in the formulation of quadraticallyconstrained quadratic optimisation problems via adjacency matrices. Using graphtheory, we transform these matrices into Binary Layered Graphs (BLG) and enterthem into the software package nauty. Nauty generates important symmetricproperties of the original problem.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.