NEOS at Wisconsin: Update on a Decade

Many optimizers are familiar with NEOS (https://neos-server.org), the online service that provides free access to both open source and commercial optimization systems (see Figure 1). NEOS was created in 1996 at Argonne National Laboratory, but since late 2010, its services have been hosted at the University of Wisconsin. Over the last year, more than 2.1 million optimization problems have been solved. This number has steadily increased each year over the past decade, demonstrating a sustained and global impact of optimization in academia and industry.

NEOS has two main components: the Server and the Guide. The NEOS Server provides a collection of optimization solvers for linear programming, mixed-integer programming, nonlinear constrained optimization, second order cone programming, and other problem formats and services. It allows users to submit an instance of a problem in a particular encoding (MPS, AMPL, GAMS, etc.) for solutions on our server farm. The NEOS Guide is a complementary site that provides broad information about optimization and a collection of case studies.

What Exactly is NEOS?

NEOS continues to function due to the continued support of both our commercial colleagues that provide access to their highly efficient solvers, and our academic colleagues that develop new approaches and push the envelope on mechanisms to effectively model and process complex problems. We remain grateful to the whole optimization community for their help in facilitating this service. The server farm at Wisconsin uses the HTCondor system to provide secure, stable and reliable access to our compute resources, in addition to sending jobs to solvers that are hosted at Arizona State University, the University of Klagenfurt in Austria and University of Minho in Portugal. The service has a number of different interfaces, including commercial modeling systems, web browsers and programmatic mechanisms that include Kestrel and XML-RPC. The Kestrel interface allows remote access to the solvers from a user’s locally installed AMPL or GAMS modeling environment, returning the results to the local modeling session. Users can also submit jobs and retrieve results using the XML-RPC application programming interface in NEOS. Although models from Pyomo and JuMP can be processed on NEOS, for security concerns, their interfaces only allow particular instance solution rather than allowing the user access to a Python or Julia shell. We have added an authenticated user option to NEOS that allows better management of resources.

To use the service, users first select an appropriate solver for their optimization problem, and then choose an appropriate input format from a list of supported ones. Then the method of submission (web, Kestrel, etc.) is set, and the user then submits their job to the NEOS Server. When the NEOS Server receives the submission, it assigns a job number and a password, and queues the job for scheduling on one of the server machines. When the job is received by a machine, the submission is unpacked, the driver processes the submission and the optimization code executes. This is managed by the HTCondor system at Wisconsin, ensuring the job runs in a sandbox that is isolated from other services. When the job finishes, the remote machine reports the results to the NEOS Server, which returns to the user via email or the user interface (i.e., for XML-RPC or Kestrel).

The NEOS Guide provides a taxonomy of different optimization problems and a suite of case studies. We are interfacing our content with complementary material from Wikipedia and try to maintain the accuracy and relevance of our content. We are always eager to engage colleagues and optimization experts in enhancing this material.

NEOS Case Studies

Optimization models can be very complex. Providing information about their use and value often requires describing application domains in which they are being deployed as was envisioned by the originators of the system.

NEOS Case Studies (https://neos-guide.org/Case-Studies) are an effort to collect a number of interesting and pedagogical problems to highlight how optimization can be used to improve strategic and operational decision-making in applied domains. We have embarked on a revitalization of this content while still highlighting existing studies provided by commercial entities associated with NEOS. We highlight several examples that were developed by the NEOS team and students at the University of Wisconsin that showcase some of the different types of problem that can be processed via optimization. Several of the new models use the Miro deployment environment, coupled to visualizations implemented with the R statistical computing tool. Each example gives some background information, solves a base case and then allows a user to interact with the data to develop intuition regarding the application. Examples include:

Air ambulance study: A simple linear programming model that reallocates helicopters to different stations to satisfy an expected demand. The model treats cases where there is both a surplus of helicopters and also excess demand for trips. Users can modify the data, including changing location information, adding helicopters and modifying trip demands. Extensions of this model to run in real time and with stochastic input data are possible.

Thundercloud example: A simple control of the trajectory of an aircraft avoiding thunderstorms (see Figure 2). It uses a minimum cost network flow formulation that makes a grid of nodes over height and time and connects the flight path at minimum cost. In the application, the user is able to change the (time and space) locations of the thunderstorm clouds, along with changing aircraft flight properties.

The classical Traveling Salesman Problem (TSP): Attempts to find a route through all the capital cities of the United States. By default we ignore visiting Alaska and Hawaii, even though that might be of primary tourist value! The case demonstrates two ways of solving the problem, one using so-called positional constraints that ensure each city has a “labeled position” in the tour, and the other implementing a classical iterative (dynamic) subtour elimination cutting procedure. Other versions of TSP models are available in the literature, and NEOS also provides access to the Concorde system that is effective for very large instances.

Facility layout problem: The goal is to move machine locations to improve the flow of materials through the system. A nonconvex constraint ensures that machines must be located a minimal distance from each other, resulting in a nonlinear programming formulation that is solved using a global solver.

Newsfeed layout problem: This problem example has similar properties to very large-scale integration (VLSI) in computer chip design. The case study demonstrates both one- and two-dimensional data instances of this problem.

Oligopolistic market design: Studied as an example of complementarity systems. This example uses concepts of Nash equilibrium, with Cournot and Stackelberg leader-follower behavior. The study attempts to explain the tradeoffs that equilibrium formulations facilitate.

COVID-19: This example has created a serious testing situation where existing resources are not sufficient for testing each individual. One solution is group testing where multiple people can be tested using resources usually needed for a single person. Once samples are collected, the model determines what group testing strategy each lab should use and how the samples should be allocated from centers to labs, obtaining as many correctly processed kits as possible.

Machine learning case study with trusted item data (see Figure 3). Training set errors can adversely affect the result and are difficult to identify. One may have the resources to verify a few trusted items. The trusted items themselves may not be adequate for learning, so we propose a bilevel programming model that uses these items to identify errors in the training set and thus improve learning. Specifically, our approach seeks the smallest set of changes to the training set labels such that the model learned from this corrected training set correctly predicts labels of the trusted items.

Other applications include math puzzles, such as Sudoku and Domino art work, classical diet problems, optimal power flow, optimization algorithm explanations, and some biological engineering examples, among others. Some of these use a Java codebase for case development and push the actual optimization solution process to the NEOS Server. The set of problems is evolving, along with the methods and environments we use to implement them on the Guide.

Usage Statistics

Usage of the system has continued to grow throughout the past decade. In the past year, the system was up for over 99% of the time, four solvers processed over 150,000 jobs each, more than 70 solvers were used, over 1 million (of 2.1 million) problems were nonlinear constrained or mixed-integer linear optimizations, and problems were submitted from more than 30 different countries (see Figure 4). In the past decade, more than 10 million jobs in total have been processed by the NEOS Server. NEOS collects models from submissions and has provided these back to the community in several ways, the most prominent of which is in collections of models for solver testing. We acknowledge the efforts of the current Wisconsin development team (which includes Jeff Linderoth, Ben Huebner, Elizabeth Wong and a host of colleagues worldwide) in maintaining the quality, breadth and reliability of the NEOS system.