3 October 2021

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.

13 September 2021

Covid-19 has caused havoc in the world's supply chains, with numerous disruptions and delays. But without sophisticated math – including a lot of linear algebra – modern supply chains would not operate at all.

The Guardian newspaper has an interesting article about the math of logistics:

Algebra: the maths working to solve the UK’s supply chain crisis.

As the article says:

The maths of logistics starts with algebra – linear algebra, to be precise. ...

Linear algebra explores solutions for sets of equations that together contain all you need to find out the relationships between the variables. ...

Logistics hasn't stood still with linear algebra, however. It has been developed into algorithms for "linear programming" and "mixed integer programming" and various other odd-sounding mathematical routines, such as "combinatorial optimisation", "greedy heuristics" and "simulated annealing". ...

And it's all done with just one purpose: to deliver to every customer, on time and in full – OTIF as it's known in the trade.

Brooks, M. (2021). "Algebra: the maths working to solve the UK’s supply chain crisis"

The article provides some insight into the hidden complexity of the systems that supply our everyday products and services. The algebra of optimization techniques, embedded within our supply chains, makes the modern world possible.

8 September 2021

Jon Lee, a Professor of Industrial and Operations Engineering at the University of Michigan, offers a free, 304 page, operations research textbook: *A first course in linear optimization*.

This textbook is a great introduction for anyone interested in learning about linear programming and integer programming.

According to the preface:

This book is a treatment of linear optimization meant for students who are reasonably comfortable with matrix algebra (or willing to get comfortable rapidly). It is not a goal of mine to teach anyone how to solve small problems by hand.

My goals are to introduce:

Lee, J. (2021). "A first course in linear optimization"

- The mathematics and algorithmics of the subject at a beginning mathematical level.
- Algorithmically-aware modeling techniques.
- High-level computational tools for studying and developing optimization algorithms (in particular, Python/Gurobi).

Download the full textbook as a PDF: A First Course in Linear Optimization (Version 4.0, August 2021)

The book's source, potentially including updates, is available at GitHub.

20 August 2021

In this article we replicate a wood-cutting model from a published academic paper, "An application of cutting-stock problem in green manufacturing: A case study of wooden pallet industry". A key motivation of the case study is the minimization of waste, as a means of reducing the manufacturer's environmental impact.

The paper's model is built in Excel and solved using OpenSolver, so we do the same. More importantly, the paper illustrates a useful pattern selection technique for formulating and solving large one-dimensional cutting problems.

We focus on replicating the paper's model – though, surprisingly, we obtain a better result.

9 July 2021

There are many tools for implementing and solving optimization models. At Solver Max we specialize in using Solver/OpenSolver in Excel and in the Python programming language, using a library such as Pyomo, CVXPY, or PuLP.

Each tool has advantages and disadvantages, including:

- Excel is, by far, the most widely-used analysis tool. It provides a visual environment for building models, with many built-in tools for analyzing and visualizing data. Excel is relatively easy to get started with, so many people are familiar with using Excel for modelling, analysis, and presentation of results. Prototyping a model in Excel is generally easier than in Python. Excel also has great depth – much more than most people realize. While Excel's grid structure makes data easy to see, its rigidity can complicate the handling of data that varies in size. Consequently, Excel models may not be as flexible as those created using a programming language.
- Python is a popular programming language. Libraries like Pyomo, CVXPY and PuLP handle much of the complexity of the optimization process (like the Solver and OpenSolver add-ins do in Excel). But learning how to program in Python can involve a steep learning curve, which is quite a barrier to entry. Consequently, far fewer people are familiar with programming in Python. Even if the optimization model developer is comfortable with Python, many model users may prefer a more familiar environment for interacting with a model.

To compare Excel and Python, we replicate a Python optimization model described in the blog How to schedule flights in Python. The source article describes the Python implementation. Here we focus on an equivalent Excel implementation. Towards the end of this article we provide a brief comparison of the two implementations.

26 June 2021

Punk Rock Operations Research has an interesting article about a 1967 paper On the art of modeling.

The paper's abstract says:

The problem of teaching or developing creative modeling ability is considered in the light of three basic hypotheses concerning the processes of enrichment (elaboration of very simple models), association (analogy with previously developed structures), and alternating attention to different aspects of the task.

Based on these hypotheses, specific steps are presented which have been developed to help individuals acquire modeling skills. The steps are illustrated by means of an example. Other sources of modeling ability are also suggested.

The discussion focuses on specific hypotheses concerning the differences between the

Morris, W. T. (1967). "On the art of modelling"teaching of modelsand theteaching of modeling.

The paper's insights and lessons are still highly relevant today, so it is definitely worth reading. We haven't found a freely available version of the paper, but it is available via ABI/INFORM or EBSCO which may be accessed through your local library web services.

17 May 2021

BCG Gamma have an interesting article that describes Five strategies for debugging MIP models.

There are many situations in which a MIP model must be debugged. The most common is when you run your model and get a message saying that it is infeasible or unbounded. Debugging can also be helpful when the model is feasible, but its solution does not behave as expected.

Five model debugging strategies:

- Inspect the .lp file. Mistakes in building the model can result in a failure to create the variables and constraints you intended. Review the .lp file to see what the solver is actually solving.
- Keep a small model instance. The .lp file size can grow very quickly. To keep the file readable, make toy models that are small enough that you can inspect the file while not being so simplistic that you lose important aspects of the real-sized model.
- Selectively remove families of constraints. The idea is to find a smaller, but still infeasible, version of your model. This allows you to identify which groups of constraints are causing infeasibility.
- Compute the irreducible inconsistent subsystem (IIS). Some solvers have an automatic method for computing which constraints cause infeasibility. The product is the smallest subset of constraints causing your model to be infeasible. Fixing the infeasibility is still a manual process.
- Use penalized artificial variables to relax constraints. An artificial variable allows a constraint to be violated, if necessary, at a cost. The relaxed system of inequalities will
*always*have a solution, enabling you to identify which constraints are causing infeasibility.

These strategies can be combined to help you debug your model.

3 May 2021

In this article we replicate an academic paper's model formulation of a COVID-19 vaccination plan for Hong Kong.

The model represents the supply of, and demand for, vaccine doses as a transportation problem, with doses "transported" from month-to-month given a storage cost rate. The objective is to minimize the total storage cost, while matching monthly supply and demand.

The paper's author solves the model using Excel and Solver. We do the same, though we also use OpenSolver – to see how it behaves differently. To incentivize the model to produce an intuitively better solution, we extend the model to include an escalating cost over time.

20 April 2021

Yet Another Math Programming Consultant (YAMPC) has a couple of interesting articles exploring different model formulations for machine scheduling problems:

- Parallel machine scheduling I, two formulations.
- Parallel machine scheduling II, three more formulations.

The situation involves scheduling 50 jobs on 4 parallel machines, with precedence relationships between jobs and multiple weighted objectives.

Five different formulations are analyzed:

- Model 1. Jobs are scheduled in discrete time slots.
- Model 2. Jobs are scheduled in continuous time.
- Model 3. A variation of Model 1.
- Model 4. A more complex variation of Model 2.
- Model 5. A positional, rather than time-based, model.

In this situation, Model 1 is the simplest and it performs the best – by a substantial margin.

YAMPC concludes that choosing the right formulation can pay off (though often we need to do numerical tests to determine which formulation is best), and having different formulations is an excellent debugging tool as they give us confidence that the results are correct.

17 April 2021

Allocating people to teams is a common task in both sport and business. Often we want the teams to be as balanced as possible. But making the allocation can be a difficult problem, especially if there are many people or we need to form several teams.

In this article we build and analyze a model that allocates 32 people to four teams, with the objective of each team having an aggregate rating that is as balanced as possible. The task is complicated by having three types of position in the teams, with a diversity of ratings across the available people.

The model is built in Excel and solved using either Solver or OpenSolver.