Abstract : (Mixed-)integer (non-)linear optimization has been one of the biggest successes in transferring mathematical insight into real-world impact. Due to the generality of the integer programming model combined with continuous improvement in solving capability, the list of industrial applications is virtually endless. While the problems are usually NP-hard in theory, in practice, an incredible number of real-world instances can be solved within seconds. The algorithmic progress outpaced the increase in computer performance by far; combined, the solver speed has exponentially grown over the last 40 years. We present the latest state-of-the-art and a glimpse into the future.
[05524] Progress in Mathematical Programming Solvers from 2001 to 2020 and future Challenges
Format : Talk at Waseda University
Author(s) :
Thorsten Koch (Technische Universität Berlin / Zuse Institute Berlin)
Abstract : We investigate the progress made in LP and MILP solver performance during the last two decades. On average, we found that for solving LP/MILP, the total speed-up was about 180 and 1,000 times, respectively.
However, these numbers considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.
Finally, we will comment on future developments.
[02270] Steepest-Edge Simplex Algorithms for Quadratic Programming
Format : Talk at Waseda University
Author(s) :
Shoji Shimizu (NTT DATA Mathematical Systems Inc.)
Koichi Fujii (NTT DATA Mathematical Systems Inc.)
Julian Hall (University of Edinburgh)
Abstract : We present steepest-edge simplex algorithms for quadratic programming problems. It is well known that in linear programming problems, the steepest-edge rule or Devex rule greatly reduces the total number of iterations in the simplex method. We extend these rules to the simplex method for quadratic programming and show their effectiveness through numerical experiments.
[02259] Techniques and advances for solving MINLPs
Format : Talk at Waseda University
Author(s) :
Robert Luce (Gurobi)
Abstract : We consider solving mixed-integer nonlinear optimization problems to global
optimality. Our solver is based on the common branch-and-bound paradigm, but
includes a number of specialized techniques to deal with nonconvex constraints
and nonconvex objective functions. In this talk we will outline a few of these
components from a theoretical and computational point of view.
[05560] News from the FICO Xpress MIP Solver and Global MINLP Solver
Format : Online Talk on Zoom
Author(s) :
Timo Berthold (Fair Isaac Germany GmbH)
Abstract : We will present the latest algorithmic advances and new features of the FICO Xpress Solver family. Next to enhanced MIP performance, a focus will be on recent new technologies like the ability to solve multi-objective optimization problems and mixed-integer nonlinear optimization problems to proven global optimality.
[02296] New MIP presolving techniques in the Cardinal Optimizer
Format : Online Talk on Zoom
Author(s) :
Gerald Gamrath (COPT GmbH)
Abstract : Presolving is an essential component of modern MIP solvers. Besides model cleanup, it identifies structures in the problem and tightens the formulation before the branch-and-cut search starts.
In this talk, we discuss common structures in real-world instances and show how a mathematical analysis of those structures resulted in new presolving reductions implemented in the Cardinal Optimizer (COPT). The impact of the new techniques is demonstrated in computational experiments.
[03882] Realization of smart factories using MIP
Format : Talk at Waseda University
Author(s) :
Hiroki Ishikura (Kyushu University)
Abstract : Smart factories have become widely used for more efficient production activities recently. In collaboration with Rohto Pharmaceutical Co. (Rohto), we have conducted research to realize smart factories. In this talk, we will introduce mobility optimization related to automated warehouses. Rohto uses an automated warehouse to manage a large volume of various items. By optimizing the mobility of automated warehouses, production activities can be streamlined, and factory operations can be made more efficient.
[02009] Benders' decomposition approach for the integrated long-haul and local VRP
Format : Talk at Waseda University
Author(s) :
Junko Hosoda (Hitachi, Ltd.)
Stephen J. Maher (Quantagonia GmbH)
Yuji Shinano (Zuse Institute Berlin )
Christoffer Villumsen (Hitachi, Ltd.)
Abstract : A supply chain management problem that integrates the determination of consolidation locations with the coordination of long-haul and local vehicle routing is a complicated problem. A Benders' decomposition approach is used to solve this problem. The delivery area and consolidation locations are computed in the master problem, and the long-haul and local vehicle routes are computed in the subproblems. The effectiveness of the decomposition is discussed in the presentation.
[05535] An efficient solver for multi-objective onshore wind farm siting and network integration
Format : Talk at Waseda University
Author(s) :
Jaap Pedersen (Zuse Insitute Berlin)
Jann-Michael Weinand (Forschungszentrum Jülich GmbH, Institute of Energy and Climate Research)
Daniel Rehfeldt (Zuse Insitute Berlin)
Abstract : Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this talk, we present an approach for the multi-objective optimization of turbine locations and their network connection using the Quota Steiner tree problem. We design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future.
