Wednesday, June 29, 2022

XNOR as linear inequalities

Boolean expressions are found in many MIP models. AND and OR are the most common. When we have an expression like $$x {\bf{\ and\ }} y$$ or $$x {\bf{\ or\ }} y$$, where all variables are binary, we typically reformulate this as a set of inequalities. XOR is a bit more exotic, but I have never seen a usage for XNOR. Until now [1].

As this is about boolean logic, in the discussion below all variables $$x$$, $$y$$, $$z$$ are binary.

Monday, June 27, 2022

Goal Programming

In [1] a goal programming [2] model was stated, although the poster did not use that term.

The model is fairly simple:

• We have 6 different raw materials that need to be blended into a final product.
• The raw materials have 4 different ingredients.
• We want to blend one unit of final product that has some target values for some formulas. We have three of these goals.

The data looks like:

Thursday, June 16, 2022

MAX-CUT

The MAX-CUT problem is quite famous [1]. It can be stated as follows:

Given an undirected graph $$G=(V,E)$$, split the nodes into two sets. Maximize the number of edges that have one node in each set.

Here is an example using a random sparse graph:

Sunday, June 5, 2022

Maximizing Standard Deviation

In [1] a question was posed: how to maximize the standard deviation of a vector $$\color{darkred}x_i$$, subject to side constraints using an LP/MIP formulation?

The standard deviation is usually defined as: $\mathbf{sd}(x) = \sqrt{\frac{1}{n-1}\sum_i \left(x_i-\mu\right)^2}$ where $\mu = \frac{\sum_i x_i}{n}$ and $$n$$ is the number of elements in $$x$$.

Thursday, June 2, 2022

A subset selection problem

Selecting $$k$$ out of $$n$$ can be a computational difficult task. Here we look at a special case and see how we can exploit the properties of the data. Suppose we have $$n$$ data points. We want to select $$k$$ points such that the average of these $$k$$ points is as close to a target value $$\color{darkblue}t$$ as possible [1]. I.e. we want $\min_{\color{darkred}S} \left| \frac{\sum_{s \in \color{darkred}S}\color{darkblue}p_s}{\color{darkblue}k} - \color{darkblue}t \right|$ where $$|\color{darkred}S|=k$$. The special property of the data is that it is composed of just a few different values. Let's say our data looks like: