13 May 2022 (289 words)
In the real world, we often encounter non-linear relationships in the systems we're modelling. But non-linearities can be difficult to model and even more difficult to solve to optimality.
The recently-published paper "Transformation and linearization techniques in optimization: A state-of-the-art survey" presents a detailed description of transformations and linearizations for a variety of non-linear relationships.
According to the paper's abstract:
To formulate a real-world optimization problem, it is sometimes necessary to adopt a set of non-linear terms in the mathematical formulation to capture specific operational characteristics of that decision problem. However, the use of non-linear terms generally increases computational complexity of the optimization model and the computational time required to solve it.
This motivates the scientific community to develop efficient transformation and linearization approaches for the optimization models that have non-linear terms. Such transformations and linearizations are expected to decrease the computational complexity of the original non-linear optimization models and, ultimately, facilitate decision making.
Asghari et al. (2022). "Transformation and linearization techniques in optimization: A state-of-the-art survey"
The transformation and linearization techniques described in the paper include:
- Multiplication of binary variables.
- Multiplication of binary and continuous variables.
- Multiplication of continuous variables.
- Maximum/minimum operators.
- Absolute value function.
- Floor and ceiling functions.
- Square root function.
- Multiple breakpoint function.
- Piecewise linear approximating functions.
- Log-linearization via Taylor series approximation.
- A new technique for linearizing square root terms by means of transformation.
The detailed descriptions in this paper make a good complement to the booklet MIP formulations and linearizations that we've mentioned previously.
Download the full paper: Transformation and linearization techniques in optimization: A state-of-the-art survey 
If you need help transforming your non-linear model into a linear model, then please contact us.
12 April 2022 (2,397 words)
In Logic conditions as constraints - Part 1 we introduced a technique for converting a broad class of logic conditions into constraints. While that technique is effective, it can be difficult to apply.
In this article, we present an alternative technique specifically designed to improve the proficiency of students learning to formulate models.
That is, we use two techniques for converting logic conditions into constraints:
- Decomposition and Translation (D&T). This technique is described in the paper "Teaching use of binary variables in integer linear programs: Formulating logical conditions".
- Conjunctive Normal Form (CNF). We described the CNF technique in Part 1.
After describing the D&T technique, we focus on replicating the paper's examples, applying both the D&T and the CNF techniques to illustrate how each technique can be applied to a variety of logic condition formulation situations.
3 April 2022 (2,424 words)
When formulating a model, we often have a situation described in terms of logic conditions where something implies something else. For example:
- If this happens, then we must do that.
- If this and that happen, then we can't do some other thing.
- We can do some or all of these things, but only if that other thing happens.
However, mathematical programming models cannot represent logic conditions directly. Therefore, we need to translate the conditions, known as "implications", into a set of constraints that represent the logic.
This article describes a technique for converting a logical implication into an equivalent set of constraints. Along the way, we'll dabble in applying some formal logic notation, define rules for manipulating formal logical implications, have a brief look at Conjunctive Normal Form (CNF), and learn how to convert CNF into constraints.
Part 2 will describe an alternative representation of this technique, specifically designed to improve the proficiency of students learning to formulate models.
7 March 2022 (191 words)
Attached is a free, 681 page textbook: Decision Modeling. The textbook is written by David M. Tulett, Associate Professor in the Faculty of Business Administration at Memorial University in Canada.
Topics covered by the textbook include: optimization of linear, integer, and nonlinear models, as well as the use of decision trees. Both Excel Solver and LINGO are used extensively to build and solve the many example models.
According to the Introduction:
Decision Modeling involves the creation of mathematical models which represent problems faced by business management. To a lesser extent, it also involves numerically solving these models. ...
If there's a difficulty with this subject, it's probably not the mathematics. Instead, the difficulty is likely to be the building of the model which the mathematics seeks to solve. The important thing is always going from a problem description to a model for the problem.
Tulett, D. M. (2022). "Decision Modeling"
Download the full textbook as a PDF (version 3.0.4, 3 March 2022): Decision Modeling
Updates for the textbook are available from Linney, Memorial University's Centre for Innovation in Teaching and Learning (CITL).
5 March 2022 (296 words)
Professor Rubin recently posted an article about finding all solutions to a network model: Finding almost all paths. The article mentions two techniques that we explored in our article Taking a dip in the MIP solution pool. Specifically, Professor Rubin says:
To find all solutions, one possible approach is to solve whatever MIP model you choose, then add a "no-good" constraint that eliminates the solution just found (and only that one) and solve again, until eventually the aggregation of "no-good" constraints makes the model infeasible. What I did instead was to use the "populate" command in CPLEX, which accumulates a pool of solutions.
An issue with the CPLEX solution pool is that it isn't guaranteed to find all optimal solutions. So, the Professor also describes a brute force method to find all solutions. The article presents analysis that demonstrates that the brute force performs better in this case – that is, the brute force method is both faster and more reliably finds all solutions.
Although clever solvers are often the best method we have, it is good to remember that brute force can be a useful – and sometimes efficient – method for solving a problem. We used a brute force method for the situation described in our article Job sequencing to minimize completion time. In that situation, brute force enumeration was very effective for small data sets, though it quickly became impractical for large data sets.
In summary, we can extend our list of techniques for finding all solutions to include:
- CPLEX solution pool.
- Eliminate known solutions.
- Brute force enumeration.
If you know of any other methods for finding all (or almost all) solutions to an optimization problem, or you want help with your own models, then please contact us.
21 February 2022 (2,177 words)
We're frequently asked questions like: "How many other optimal solutions exist?" and "How do I find those solutions?". Often these questions are prompted by our mentioning that most models have alternative optima – that is, optimal solutions with the same objective function value, but different variable values.
Although a model may have a unique optimal solution, models with integer/binary variables typically have multiple optimal solutions, and continuous linear models may have an infinite number of alternative optimal solutions. The likely existence of multiple alternative optima is why we usually say "an optimal solution", rather than saying "the optimal solution".
Sometimes people also ask, "How do I find solutions that are almost optimal?". This question typically indicates that the decision maker may accept a sub-optimal solution (or an alternative optimal solution) that is "better" according to some criteria that aren't captured by the model design. Of course, we should look at incorporating the unspecified criteria within the model, but sometimes that is difficult or even impossible. In any case, exploring the solution space around the optimal solution is an important part of the modelling process.
This article describes methods for finding alternative optima and solutions that are almost optimal. Specifically, we explore the CPLEX "solution pool" feature, which NEOS Server has recently made available through their online portal.
29 January 2022 (149 words)
When formulating a model, many of the problems we encounter involve non-linear formulae. For example, a fixed cost is incurred only if a facility is built, or a variable can take values only in the ranges 5 to 10 or 80 to 100.
Optimization models work best when the objective function and constraints are all linear. In some situations, it is possible to reformulate a model to linearize the non-linear parts. The techniques for linearizing non-linear formulae can make the difference between a model being viable or not.
FICO Xpress Optimization have written a booklet that describes a variety of useful mixed-integer programming (MIP) formulations and linearizations, including:
- Binary variable logical conditions.
- Minimum, maximum, and absolute value of binary variables.
- Multiplication of variables.
- Variables with disjunctions.
- Batch sizes.
- Minimum activity level.
The booklet is available at: MIP formulations and linearizations.
17 December 2021 (200 words)
The COIN-OR Foundation is seeking support to continue providing open-source optimization software for the operations research community. They have published an article, Future of COIN-OR, describing their challenges in securing funding and the participation of community members to continue operating.
COIN-OR are responsible for the development of more than 70 projects that are widely used in optimization tools, including:
- Pyomo, a Python-based optimization modeling language.
- PuLP, a Python library for linear optimization.
- CBC, the default mixed integer linear programming solver used in OpenSolver and elsewhere.
- Bonmin and Couenne, non-linear mixed integer programming solvers.
The COIN-OR Foundation presents three possible future directions:
Option 1: Wind down the COIN-OR Foundation activities related to maintenance and development of common infrastructure and existing codes that are not otherwise maintained.
Option 2: Continue operating in a haphazard fashion and hope that the community will eventually take up the cause as things slowly degrade.
Option 3: Find a path to funding the current activities of the COIN-OR Foundation in a sustainable way.
To achieve Option 3, the Foundation needs your support. You can either donate to COIN-OR, or email them at
2 December 2021 (1,879 words)
Project crashing is the process of compressing a project plan by using additional resources to reduce the duration of some tasks.
Using additional resources incurs additional cost, so it is important that the resources are deployed to the tasks that produce the greatest benefit. A project manager must decide an appropriate trade-off between time and cost for each task, leading to the best revised project plan. Given the dependencies between project tasks, making these trade-offs can be complex and difficult, even for a small project.
This article describes an example of project crashing using an optimization model to help the project manager decide what to do.
16 November 2021 (2,326 words)
Recently we were working on a small one-dimensional bin packing model. The situation was simple, and we expected the model to be easy to solve. But there was just one problem: we couldn't find an optimal solution, even after letting the solver run overnight for 12 hours.
Initially, we were using the CBC solver. Since that didn't work, we tried CPLEX via NEOS, but we encountered the same problem – CPLEX couldn't find an optimal solution either.
So, we searched the Operations Research literature for an alternative formulation. We discovered a recently published academic paper that has a new, innovative formulation for one-dimensional bin packing (and potentially other types of packing situations).
This article describes the new formulation and our experience applying it to our simple, yet difficult to solve, model.
5 November 2021 (199 words)
There are many tools for building an optimization model, including:
- Excel/OpenSolver, which provides a familiar, interactive, visual grid for modelling.
- Python, plus the CVXPY or PuLP library, which provides a programmatic way to define a model.
Each tool has advantages and disadvantages, as we discussed in Optimization in Excel vs Python.
The tool CMPL (<Coliop|Coin> Mathematical Programming Language) occupies an intermediate position. That is, CMPL combines the advantages of working with the data and solution in Excel, while providing the power and flexibility of a programming language for defining the model.
According to the tool's website:
The CMPL syntax is similar in formulation to the original mathematical model but also includes syntactic elements from modern programming languages. CMPL is intended to combine the clarity of mathematical models with the flexibility of programming languages.
Steglich, M. (2021). "Optimisation Modelling with Excel and CMPL2"
CMPL has recently been updated to version 2.0, as described in the paper "Optimisation modelling with Excel and CMPL2". The paper provides a good overview of CMPL, including a couple of examples to help you get started*.
* Note that there's a bug in the paper's transhipment example. You'll need to add minCap[edges] to the definition in line 01 of Listing 7.
7 October 2021 (144 words)
Vamshi Jandhyala has an interesting series of blog posts about Optimization using linear models.
Each article includes a description of the topic, along with several examples written in Python and solved using the Gurobi commercial solver:
- Modeling using Linear Programming. Illustrates some concepts of linear programming via the formulation and solution of a resource allocation problem.
- Modeling using Integer Programming. Describes several applications of integer programming, including an assignment problem, graph coloring, the 0-1 knapsack problem, a set covering problem, and a class scheduling example.
- Graphs and Integer Programming. Explores some graph theory applications of integer programming, including finding a maximal independent set and finding the maximal clique of a set.
The examples include Python source code, though they are sufficiently small that they could be translated to use your preferred modelling tool and solver.
3 October 2021 (2,419 words)
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 (202 words)
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 (157 words)
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 (2,502 words)
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 (1,530 words)
There are many tools for implementing and solving optimization models. At Solver Max we specialize in using Solver/OpenSolver in Excel. Another popular tool is the Python programming language, using a library such as 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. 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 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.
26 June 2021 (172 words)
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 teaching of models and the teaching of modeling.
Morris, W. T. (1967). "On the art of modelling"
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 (280 words)
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 (1,664 words)
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.
