Wednesday, August 10, 2022

Large sparse transportation model with CVXPY,CVXR

In [1] I was trying out different formulations of a large, sparse (but very easy) transportation model using different modeling tools and solvers. The conclusion was:

  • Exploiting sparsity leads to the best performance
  • GAMS/Cplex is about 10 times as fast as Python/PuLP/CBC
  • GAMS/Cplex is about 1000 times as fast as R/OMPR/GLPK

Don't overinterpret these numbers: this is a single model, which may not be at all representable for your models. Let's see how CVXPY[2] and CVXR[3] are doing. To recap we want to solve a large (but easy) transportation model:

Dense Transportation Model
\[\begin{align}\min&\sum_{i,j}\color{darkblue}c_{i,j}\cdot\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j} \le \color{darkblue}a_i && \forall i \\& \sum_i \color{darkred}x_{i,j} \ge \color{darkblue}b_j && \forall j \\ & \color{darkred}x_{i,j} \ge 0 \end{align}\]

The additional wrinkle is that only a small fraction of the links \(i \rightarrow j\) exist.

There are (at least) three ways to model this:

  1. Use a large cost coefficient for forbidden links.
  2. Fix \(\color{darkred}x_{i,j}=0\) for non-existing links.
  3. Exploit sparsity directly by only summing over existing links.
CVXPY/CVXR are matrix-based modeling tools. That gives some extra things to think about. A transportation model in matrix-notation can look like:


Transportation Model in Matrix Notation
\[\begin{align}\min\>&{\bf tr}(\color{darkblue}C^T\color{darkred}X)\\&\color{darkred}X\color{darkblue}e \le \color{darkblue}a \\ & \color{darkred}X^t\color{darkblue}e \ge \color{darkblue}b \\ & \color{darkred}X \ge 0 \end{align}\]

Monday, August 1, 2022

Curl.exe

Newer versions of Windows come with a very useful tool to download files: curl.exe.

The standard help is:

C:\Users\erwin>where curl

C:\Windows\System32\curl.exe

             

C:\Users\erwin>curl --help

Usage: curl [options...] <url>

 -d, --data <data>          HTTP POST data

 -f, --fail                 Fail fast with no output on HTTP errors

 -h, --help <category>      Get help for commands

 -i, --include              Include protocol response headers in the output

 -o, --output <file>        Write to file instead of stdout

 -O, --remote-name          Write output to a file named as the remote file

 -s, --silent               Silent mode

 -T, --upload-file <file>   Transfer local FILE to destination

 -u, --user <user:password> Server user and password

 -A, --user-agent <name>    Send User-Agent <name> to server

 -v, --verbose              Make the operation more talkative

 -V, --version              Show version number and quit

 

This is not the full help, this menu is stripped into categories.

Use "--help category" to get an overview of all categories.

For all options use the manual or "--help all".

 

C:\Users\erwin>


A model with semi-continuous variables

In [1], a selection problem is posted, that turns out to be an easy MIP. The problem is:

From a (large) collection of products select those products with the highest unit return (or value) subject to:
  • A product can only be ordered between a minimum and maximum amount
  • There is a budget w.r.t. the total amount of products
This can be modeled using so-called semi-continuous variables: variables that can assume zero or a value between the constants \(\color{darkblue}L\) and \(\color{darkblue}U\). So we can write:


MIP model with semi-continuous variables
\[\begin{align} \max & \sum_i \color{darkred}x_i \cdot \color{darkblue}{\mathit{rate}}_i \\ & \sum_i \color{darkred}x_i \le \color{darkblue}{\mathit{budget}} \\ & \color{darkred}x_i \in \{0\}\cup [\color{darkblue}L_i,\color{darkblue}U_i] \end{align} \]

Tuesday, July 19, 2022

The inverse of A(i,j) has signature B(j,i)

GAMS has strict domain checking (type checking). This has some interesting consequences. Basically all good: much better protection against errors compared to simply using integer indices \(1,\dots,n\). Consider the square matrix \(\color{darkblue}A_{i,j}\):


set
  i
/a,b,c,d/
  j
/1,2,3,4/
;
parameter A(i,j) 'square matrix';
A(i,j) = min(
ord(i),ord(j));
display A;

Tuesday, July 12, 2022

Linearize min(a,b)>min(x,y)

This question was posed [1]: How to linearize \[\min(\color{darkred}a,\color{darkred}b)\gt \min(\color{darkred}x,\color{darkred}y)\] where \(\color{darkred}a,\color{darkred}b,\color{darkred}x,\color{darkred}y\) are variables. The type of variables is not specified so let's assume they all are continuous variables.

Monday, July 11, 2022

Transportation model with some non-existing links

I am again looking at simple models based on the transportation model:

Dense Transportation Model
\[\begin{align}\min&\sum_{i,j}\color{darkblue}c_{i,j}\cdot\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j} \le \color{darkblue}a_i && \forall i \\& \sum_i \color{darkred}x_{i,j} \ge \color{darkblue}b_j && \forall j \\ & \color{darkred}x_{i,j} \ge 0 \end{align}\]


Friday, July 8, 2022

Artificially creating a large LP model: why is Cplex so efficient

I am teaching some GAMS classes this summer. The first class is about the transportation model. This is model number 1 from the GAMS model library [1]. It is a tiny model, slightly modified from the original model in [2]. I believe the GAMS version has been made dual degenerate.



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.   

AND  

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: