I am a full-time consultant and provide services related to the design, implementation and deployment of mathematical programming, optimization and data-science applications. I also teach courses and workshops. Usually I cannot blog about projects I am doing, but there are many technical notes I'd like to share. Not in the least so I have an easy way to search and find them again myself. You can reach me at erwin@amsterdamoptimization.com .
We can formulate a linear least squares regression model as an optimization problem. This is not how these problems are solved in statistical packages. Often, they use a QR decomposition. A real optimization formulation can be useful when we need to add unusual constraints that the statistical package does not support directly, or when we need to optimize a special maximum-likelihood function.…
In this post, I want to discuss indicator constraints and how to replace them with simple multiplications. As we shall see, this is a somewhat harebrained but still interesting idea. Indicator constraints are implications of the form: \[\delta=0 \implies \text{linear constraint}\] or \[\delta=1 \implies \text{linear constraint}\] where \(\delta \in \{0,1\}\) is a binary decision variable. There…
In this post, let's do some experiments with the "hostile brothers problem." We have a plot of land. In my test models \([L,U]\times [L,U]\) with \(L=0\), \(U=100\)). We want to place \(n\) brothers on this plot. As they don't get along, we want to spread them out by maximizing the distance between neighbors. In modeling terms, we create a maximin model that maximizes the minimum distance between…
Here, I delve into the problem of finding the largest empty rotated square . Given \(n\) data points, find the largest square rotated by an angle \(\theta\), such that the square does not contain any of the points. In [1], I discussed two special cases: an axis-aligned square (angle is 0°), a diamond shape, which is a square rotated by 45°. Here we focus on arbitrary angles. A picture can help a…
Finding the largest empty shapes This post is about finding empty regions (square, rectangle, or circle) in a (large) collection of given points. These are interesting little optimization problems. Data I generated \(n=100\) data points \((x_i,y_i), i=1,\dots,n\) drawn from a uniform distribution \[\begin{align}&x_i \sim U(0,10) \\ & y_i \sim U(0,10)\end{align} \] It is always a good idea to have…
Convex hull as an optimization problem In the previous posts, the construction of a convex hull played a significant role: it was an easy way to reduce the size of the data sets, often by a large amount. Somehow, it escaped me that we can try to formulate this as what turns out to be a conceptually rather simple optimization problem. This has probably little or no practical value. But it remains…
In [1] where I discussed how to find the minimum enclosing circle and minimum enclosing ellipse around a set of points. This is a follow-up post where I extend this to sets of circles and ellipses. 1. MINIMUM ENCLOSING CIRCLE Here our data is a set of \(n\) circles (or disks) of different size. We want to find the smallest circle that contains all these circles. An example data set with random…
Minimum encompassing circle and ellipse This is again about finding the smallest geometric shape containing all our data points. Here I focus on easy, convex cases: a circle and an ellipse. After the last post, where I was struggling mightily with a non-convex version of this model, this should be a breeze. I'll discuss SDP (semidefinite programming), SOCP (second order cone programming), rotated…
Minimum encompassing triangle This looks like a simple problem. Given \(n\) 2d points, find the smallest encompassing triangle. I follow the formulation from [1]. This post is self-contained, so you don't have to go back to [1]. The main contribution here is how one could work around the performance issues of the original formulation. Summary The problem can be formulated as a nonconvex quadratic…