Where can I find documentation on good practices for efficient formulations of a problem?

Question

I am sort of new to mathematical optimization and have to build some fairly complicated models for my thesis. I was wondering where I could find literature to help me develop more efficient versions of them. I'm thinking of general good practices in the field, common solutions to constraints that are usually a bottleneck in the computations. For example, avoiding non-linear constraints in our formulations, by linearizing the product of a binary and a continuous, as it is generally a good practice, as far as I know.

To summarize, I'm confident that my methods yield the correct results, but would like equivalent (or weaker but sufficiently strong) formulations that are more efficient.

If it helps, the problem I'm dealing with is to find the best time to schedule maintenance in order to minimize costs, subject to a bunch of constraints.

Here, Gualandi mentions Model Building in Mathematical Programming which I will definitely take a look. Are there any more books or websites/forums on the topic?

EDIT:

I also found Speeding up Energy System Models - a Best Practice Guide, which seems to answer my question as well, but I haven't looked into it yet.

Answer 1

In my opinion, @Erwin Kalvelagen's blog is a great resource for learning mathematical modeling.

He posts a variety of tricks and tips, compares different models with one another, different solvers, etc.

What is great about the blog is that its not just textbook theory, its operational research exploration which challenges and/or verifies textbook theory.

Otherwise I recommend the famous Network Flows book by Ahuja et al.

Answer 2

Honestly, there is not that much in general that I am aware of. The best resource (other than the ones you mentioned) that comes to mind is Fischetti's modeling book "Introduction to Mathematical Optimization", which gives a good overview over many standard problems and various formulations.

Otherwise I can recommend some specific ones:

• LP tricks by AIMMS
• MIP tricks by AIMMS
• Modeling cookbook by MOSEK

Answer 3

You might find OptaPlanner's domain modeling guide (Docs section 20.2) useful.

It's a step by step guide on how to design a good model - and explains why some models are better or worse than others. Here's a few examples of good vs bad models:

Answer 4

I would also add "Optimization in Engineering" as a reference. It offers a good overview on LPs, MILPs and convex programming, focusing on applications. It is also a good resource in best practises, see for example Chapter 3.3 "Linearizing Nonlinearities Using Binary Variables".

Answer 5

There's also the Octeract Reformulator repository, where we host a growing collection of scripts to automatically apply reformulations to non-linear problems, e.g.:

from octeract import *

# Linearize bilinear term x*y where x,y binary
# =============================================
# x*y = w
# w <= x
# w <= y
# x + y - 1 <= w
# 0 <= w <= 1
# =============================================

# Define symbolic trigger
my_trigger = Match('C(n)*V(x)*V(y)') 

# Filter binaries 
my_filter = (IsBinary('x') & IsBinary('y'))

# Specify how to change the model
# Add auxiliary variable with the same bounds as x*y
add_auxiliary_var = AddBinaryVariable('w_xy')
substitute_term = SubWith('n*w_xy')
add_constraint0 = AddConstraint('w_xy <= x')
add_constraint1 = AddConstraint('w_xy <= y')
add_constraint2 = AddConstraint('x + y - 1 <= w_xy')

add_constraints = add_constraint0 + add_constraint1 + add_constraint2

# Add all modifications 
my_actions = add_auxiliary_var + substitute_term + add_constraints

# Create mod
LinearizeBilinearBinaryBinaryMod = (my_trigger & my_filter).then(my_actions)

The language is human readable so it's easy to understand/modify what's happening, and the reformulations can be automatically applied to any problem. For instance, this script will automatically linearise any Binary Quadratic problem:

from octeract import *
from LinearizeBilinearBinaryBinary import LinearizeBilinearBinaryBinaryMod
from LinearizeBilinearContBinary import LinearizeBilinearContBinaryMod
from LinearizeSquaredBinary import LinearizeSquaredBinaryMod

m = Model()

m.add_variable("y1", 0, 1, BIN)
m.add_variable("y2", 0, 1, BIN)
m.add_variable("y3", 0, 1, BIN)
m.add_variable("x", -10, 10)
m.minimize("2*y1*y2 + 3*x*y1 + y1^2")

m.set("y2*y3 + y2*x + 5*y2*y1 - 5*y2^2").to(0)

print(m)

m.apply_mod(LinearizeBilinearBinaryBinaryMod)
m.apply_mod(LinearizeBilinearContBinaryMod)
m.apply_mod(LinearizeSquaredBinaryMod)

print(m)

Answer 6

For the case of mixed integer programs, I would recommend the following paper:

Klotz, E., & Newman, A. M. (2013). Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science, 18(1-2), 18-32.

As the abstract says:

"Even with state-of-the-art hardware and software, mixed integer programs can require hours, or even days, of run time and are not guaranteed to yield an optimal (or near-optimal, or any!) solution. In this paper, we present suggestions for appropriate use of state-of-the-art optimizers and guidelines for careful formulation, both of which can vastly improve performance."

I hope it helps.