Solver Max - We need more power: NEOS Server

3 October 2021

Gorilla

OpenSolver uses the free, open-source CBC solver. For most linear models, CBC is good enough. But sometimes CBC struggles to solve a model in a reasonable time. That usually happens when the model has a large number of variables or constraints, though some small models can also be difficult to solve.

When CBC doesn't get the job done, we can try using a more powerful solver. One way to apply more power is to use the NEOS Server, which is an online service that provides access to many different solvers, including commercial solvers, for free.

This article describes an example of how we can solve a model using the CPLEX solver via the NEOS Server.

Download the model

The model is available on GitHub.

Situation

We want to form 5 teams from a pool of 30 people. All teams will consist of 6 people, and each person will be assigned to one team.

Each person is rated on a scale from 1 (low) to 100 (high) for three attributes: experience, qualifications, and tenure. We want the teams to be as balanced as possible, considering each of the attributes and overall.

We want to weight the attributes, with the highest weight on the team's overall score (sum of the individual attributes), then on each of the attributes in declining order: experience, qualifications, and tenure. For example, we might weight the attributes as follows: 10 for overall score, 5 for experience, 2 for qualifications, and 1 for tenure.

This situation is similar to an earlier example model, Allocate people to balanced teams, except that we have three skill attributes rather than three tiers of team members.

Model design

Formulation

The mathematical formulation for our model is shown in Figure 1. That is:

Equation (1). Minimize the weighted range of skills across the teams.
Equation (2). Each person must be allocated to one team.
Equation (3). The number of people allocated to each team equals the requirement for that team.
Equation (4). The skills for each team must be greater than or equal to the lower bound for that attribute.
Equation (5). The skills for each team must be less than or equal to the upper bound for that attribute.

Figure 1. Mathematical formulation

\begin{alignat*}{1} &\text{Objective} \\ & \quad \text{Min } fObjective &=\quad &\sum_{a=1}^k \text{dWeight}_{a} \times \left( vSkills_{a}^{UB} - vSkills_{a}^{LB} \right) \tag{1} \\ &\text{Subject to} \\ & \quad \sum_{t=1}^n vAllocation_{p,t} &= \quad &1 \quad &\forall \ p \in P \tag{2}\\ & \quad \sum_{p=1}^m vAllocation_{p,t} &= \quad &\text{dPeopleRequired}_{t} \quad &\forall \ t \in T \tag{3}\\ & \quad \sum_{p=1}^m \left( \text{dAttributes}_{p,a} \times vAllocation_{p,t} \right) \ &\geq \quad &vSkills_{a}^{LB} \quad &\forall \ a \in A, \forall \ t \in T \tag{4}\\ & \quad \sum_{p=1}^m \left( \text{dAttributes}_{p,a} \times vAllocation_{p,t} \right) \ &\leq \quad &vSkills_{a}^{UB} \quad &\forall \ a \in A, \forall \ t \in T \tag{5}\\ \\ &\text{Variables} \\ & \quad vAllocation_{p,t} &= \quad &\begin{cases} 1, \text{if person $p$ is allocated to team $t$} \\ 0, \text{otherwise} \tag{6} \end{cases} \quad &\forall \ p \in P, \forall \ t \in T\\ & \quad vSkills_{a}^{LB} &= \quad &\text{Positive integer} \quad &\forall \ a \in A \tag{7}\\ & \quad vSkills_{a}^{UB} &= \quad &\text{Positive integer} \quad &\forall \ a \in A \tag{8}\\ \\ &\text{Data} \\ & \quad \text{dWeight}_{a} &= \quad &\text{Positive real} \quad &\forall \ a \in A \tag{9}\\ & \quad \text{dPeopleRequired}_{t} &= \quad &\text{Positive integer} \quad &\forall \ t \in T \tag{10}\\ & \quad \text{dAttributes}_{p,a} &= \quad &\text{Positive integer, score 1$\ldots$100} \quad &\forall \ p \in P, \forall \ t \in T_{k-1} \tag{11}\\ & \quad \text{dAttributes}_{p,a} &= \quad &\sum_{a=1}^{k-1} \text{dAttributes}_{p,a} \quad &\forall \ p \in P, a=k \tag{12} \\ &\text{Sets} \\ & \quad A &\ &\text{Attribute} \tag{13} \\ & \quad P &\ &\text{Person} \tag{14} \\ & \quad T &\ &\text{Team} \tag{15} \\ \\ &\text{Dimensions} \\ & \quad k &\ &\text{Number of attributes} \tag{16} \\ & \quad m &\ &\text{Number of people} \tag{17} \\ & \quad n &\ &\text{Number of teams} \tag{18} \\ \\ &\text{Bounds} \\ & \quad \text{Non-negative} &\ &\quad \tag{19} \\ \end{alignat*}

Implementation

Skills balance

The model implementation is fairly straightforward. First, we characterise the skill balance requirement as an objective that sums:

The team skill score = sum of team member scores across the skills.
Individual skill scores = sum of team member scores for each of the 3 skills.

Assign people to teams

Then people are assigned to teams via a table of binary variables for person by team. Each person can be allocated once. Each team consists of 6 people.

The interesting part of this model, as shown in Figure 2, is that integer variables represent bounds on the high and low score for each individual skill and team skill total. The team skills are constrained by these variables, with an objective in terms of the range between the high and low scores. Minimizing the sum of the weighted ranges makes the teams as balanced as possible.

This type of model can be difficult to solve, as we will see.

Solver model

Objective function

The Solver model is shown in Figure 3. Our objective is to minimize the sum of the weighted skill ranges across all teams.

Variables

The model has three sets of variables:

vAllocation. A binary variable for each possible combination of person and team.
vSkillsLower. Integer variables for minimum team skills for each attribute and overall.
vSkillsUpper. Integer variables for maximum team skills for each attribute and overall.

Constraints

The constraints are:

fPeoplePerTeam = dPeopleRequired. Each team must have the required numer of people.
fSkillsPerTeam <= fSkillsUB. The skills for a team must be less than or equal to this variable upper bound.
fSkillsPerTeam >= fSkillsLB. The skills for a team must be greater than or equal to this variable lower bound.
fPersonAllocation = 1. Each person must be allocated to exactly one team.
vAllocation = binary. Set allocation of person to team to be binary.
vSkillsLower = integer. Set lower skills bounds to be integer.
vSkillsUpper = integer. Set upper skills bounds to be integer.

Solving the model with CBC

All the model's relationships are linear, so we can use the CBC solver via OpenSolver.

However, as shown in Figure 4, CBC struggles to find a proven optimal solution.

Initially, CBC quickly finds a series of good solutions. But then progress slows dramatically. After 78 minutes, CBC finds a solution with an objective function value of 82, though that solution is far from proven optimal.

By definition, a solution is proven optimal when the best solution found equals the bound on the best possible solution. In this example, it takes almost 5 hours for CBC to start improving the lower bound on the best possible solution. After 10 hours, there is still a substantial gap between the best solution found and the bound on the best possible solution.

Figure 4. CBC's progress is initially good, but then very slow

Perhaps CBC would eventually find a proven optimal solution, if we let it run for long enough. But that could take a very long time. Alternatively, we can apply a more powerful solver to see if it works better. That's where NEOS Server is very useful.

Overview of NEOS Server

NEOS (Network-Enabled Optimization System) Server is a free, internet-based service for solving numerical optimization problems. The service is hosted by the University of Wisconsin, with a distributed network of high-performance computers located in several locations around the world.

NEOS provides access to more than 70 solvers for 18 types of problem. Models are submitted through an online portal or via an Application Programming Interface (API). For example, OpenSolver can use the API to submit models and retrieve results.

Whether using the portal or the API, each model submitted to NEOS is assigned a job number and a password, which you can use to access detailed results. You are required to include an email address as part of your model submission.

Characteristics of NEOS Server include:

You should consider that jobs submitted to NEOS are public.
Each job is limited to 3 GB of RAM.
Input file size is limited to 16 MB, and any output produced by the solver is limited to 100 MB.
Multi-threaded solvers are limited to a maximum of 4 threads per job.
Maximum run time is 8 hours per job.

In addition, NEOS is a shared resource, so a job may be queued before starting to be processed. The elapsed run time may vary depending on how busy the servers are.

Additional information about using NEOS Server is available in the NEOS terms of service.

Submitting a job to NEOS

Using NEOS from within OpenSolver

We can submit a job to NEOS from within OpenSolver. In this example, we want to use the commercial solver CPLEX, to see if it is more successful than CBC in finding a proven optimal solution to our model.

CPLEX is subscription-based commercial software, with pricing that starts at US$199 per month per user. Being able to access this software – and many other solvers – via NEOS, for free, is a very valuable service.

The procedure for using NEOS from within OpenSolver is as follows:

Build the model as usual.
Under the menu Data > OpenSolver > Model > Solver Engine select "NEOS using CPLEX (Linear solver)" from the list of solvers, as shown in Figure 5.
Under the menu Data > OpenSolver > Model > Options enter your email address in the "Email address for NEOS solvers" field.
Solve your model.
If NEOS returns a solution, then it will be automatically loaded into the spreadsheet.

Using NEOS from within OpenSolver is the simplest way to use the CPLEX solver. However, in our experience, accessing NEOS via OpenSolver is unreliable. Sometimes it works, but often it fails. Even when OpenSolver is able to retrieve a result, there is little or no feedback about the solution. Therefore, we prefer to use the NEOS online portal.

Using NEOS via the online portal

NEOS Server provides access to a wide range of solvers. Each solver has specific requirements for input files and how the results are returned.

In this example, we want to use CPLEX to solve our model. So, we need a model to upload to NEOS. We can use CBC to generate a model file, in a suitable format, as follows:

Build the model as usual.
In OpenSolver, set the solver engine to be "COIN-OR CBC (Linear solver)".
Set the OpenSolver time limit to be a small number, like 5 seconds (because we don't want the CBC solution).
Select the OpenSolver option "Show optimisation progress while solving".
Solve the model.
Copy the location of OpenSolver's temporary folder – which is specified near the top of the progress dialog as "Startup directory".
Close the progress dialog.

Note that the exact path of the temporary folder may depend on your system settings. As shown in Figure 6, the path of our temporary folder is "C:\Users\SolverMax\AppData\Local\Temp\OpenSolver-E99A\". Note that the last 4 characters of the folder's path change from Excel session to session.

Figure 6. Location of OpenSolver's temporary folder

Open the temporary folder and note that, amongst other files, it contains a file called model.lp. This file contains a plain text definition of our model. The .lp file format used by CBC is compatible with CPLEX – for more information, see LP file format.

Next, open the NEOS Server website in a browser. It is worthwhile looking around the NEOS website, as they provide useful information about their service, the solvers that are available, and optimization modelling in general.

To get started using NEOS, select the "Submit a job to NEOS" link, as shown in Figure 7.

The NEOS website will load a page that lists the problem types that it can handle and the solvers that are available. Our model is a Mixed Integer Linear Program, and we want to use CPLEX. So, scroll down the list to the "Mixed Integer Linear Program" section and locate the CPLEX line. Then select the "[LP]" link to open the NEOS CPLEX webpage for a .lp input file.

In the "Web submission form":

Select your model.lp file.
Select the option to "Return a .sol file".
Enter your email address.
Click the "Submit to NEOS" button.

NEOS will present a list of jobs that are currently running. Your job will be listed at the bottom of the page, including a job number and password – these can be used to access detailed results, if needed.

Once NEOS has finished running the job, you'll receive an email containing a link to the .sol result file that you requested. Open the link and save the .sol file somewhere convenient.

The plain text .sol file contains details of the solution, in xml format. Part of our solution file is shown in Figure 8. OpenSolver defines variable names using their cell address; CPLEX returns the results using those cell addresses.

Figure 8. Extract from the .sol file

    <variables>
     <variable name="H47" index="0" value="1"/>
     <variable name="I47" index="1" value="-0"/>
     <variable name="J47" index="2" value="-0"/>
     <variable name="K47" index="3" value="-0"/>
     <variable name="L47" index="4" value="-0"/>
     <variable name="H48" index="5" value="-0"/>

We now need to read the solution into our spreadsheet. The example spreadsheet includes some VBA to read the .sol file. Note that this code does little or no error checking or validation, so use with care and at your own risk.

The central part of the VBA code is shown in Figure 9. Since the .sol file is in xml format, it is straightforward to parse the file and read the solution into the spreadsheet.

Figure 9. Part of VBA code to load CPLEX result from NEOS

    XMLFile.Load (FileName)
    Status = XMLFile.SelectNodes("//header").Item(0).Attributes _
        .getNamedItem("solutionStatusString").Text
    Set Variables = XMLFile.SelectNodes("//variables/variable")
    For Each CurrVariable In Variables
      VarName = Replace(CurrVariable.Attributes.GetNamedItem("name").Text, "_", "")
      VarValue = CDbl(CurrVariable.Attributes.GetNamedItem("value").Text)
      Range(VarName).Value = VarValue
      NumVariables = NumVariables + 1
    Next CurrVariable

Note that for each variable name that includes the letter "E" or "e", alone or followed by other valid symbols, or followed by another "E" or "e", OpenSolver precedes the name with an underscore. It does this to avoid confusion with using E as notation for exponents in numerical values. For example, cell "E48" is written as "_E48". In the xml file this appears as name="_E48". The VBA removes the underscores when it extracts the call names, so that it can use the names as cell addresses.

To use the VBA to load the solution file:

Ensure that the model worksheet is active.
Run the VBA procedure ReadNEOSResultCPLEX.
When asked, select the saved .sol file.

After parsing the NEOS solution file, the VBA will indicate the solver's status along with the number of variables imported.

CPLEX solution

Following the NEOS Server procedure above, CPLEX returns an optimal solution in about 20 seconds. The optimal solution has an objective function value of 82, the same as the best solution found by CBC. That is, CBC did find an optimal solution (albeit much slower than CPLEX), but it was unable to prove optimality in a reasonable time.

As shown in Figure 10, CPLEX finds better solutions faster than CBC, and CPLEX improves the bound much faster. When the best solution and the bound meet, after 20 seconds, the best solution is proven to be optimal.

Note that the performance difference between CBC and CPLEX is not usually so large. Part of the difference is due to the NEOS Server computers being faster than our PC. But most of the performance difference is due to commercial solvers generally being faster than open-source solvers.

Figure 10. CPLEX finds an optimal solution in 20 seconds

It isn't always necessary to go through the entire procedure described above. Often we just want to confirm that a solution found by CBC is optimal. In that circumstance, we can run the model.lp file on NEOS, without loading the .sol file, to check that the optimal objective function values found by CBC and CPLEX are the same.

Conclusion

The free CBC solver, included with OpenSolver, is sufficient for most models. But sometimes we need more solving power.

Using the procedure described in this article, we can use the NEOS Server to access a wide range of solvers – including powerful commercial solvers like CPLEX. This allows us to tackle a wider range of models, enabling us to improve our modelling and decision making.

If you would like to know more about this model, or you want help with your own models, then please contact us.

We need more power: NEOS Server