Monday, May 23, 2022

Symmetry detection for MIPs in MOSEK 10

Remember counting ladybug spots as a child? If you realized ladybugs were symmetric, you could save some work by counting on one wing only and multiplying by two. In Mixed Integer Programming, something similar applies. If we detect symmetries in a problem formulation, we may be able to save some computational effort and thus time when solving it. But first of all, what are symmetries in a MIP formulation? Different from the geometric symmetry of a ladybug, the notion of symmetries in MIP may be thought of as the presence of equivalent solutions.

They can arise, for example, when identical physical objects are described distinctively in a model. As an example, take the MISOCP models for geometric facility location problems described here. Roughly speaking, the task there is to cover a set of given points in the plane with disks to be placed at will. Say we have 10 points and 3 fixed-radius disks, and want to cover as many points as possible. In a straightforward model, we would assign indexes $i = 1,2,3$ to the disks, and indexes $j = 1,...,10$ to the points, and then define all sorts of variables like $x_{ij} \in \{0,1\}$, stating whether disk $i$ covers point $j$. What we did here is assign labels to the disks, making them a blue, a red and a green one, say. But if all three disks have the same radius, this gives rise to equivalent solutions, see Figure 1. For the cost of a solution, it is only important whether a certain point is covered, but not by which disk.

Figure 1: Equivalent disk covering solutions

Symmetry breaking inequalities, orbital branching and fixing, or Isomorphism pruning are just some of the various techniques that have been studied over the years to better address symmetries in MIP. Variants of some of these various techniques have been implemented in the latest MOSEK version 10. Figure 2 sketches the effect on solution times of completely switching off symmetry detection and handling with the user parameter MSK_IPAR_MIO_SYMMETRY_LEVEL on the so-called Margot instances, known to be highly symmetric.
Figure 2: Solving Margot's instances w/ and w/o symmetry detection

Some of the techniques in question can be extended from Mixed Integer Linear to Mixed Integer Conic Programming, or more generally Mixed Integer Nonlinear Programming. We sometimes advocate that one nice feature of (Mixed Integer) Conic Programming is the separation of data and structure, and implementing symmetry detection is an aspect where this comes in handy. All data involved in a model is contained in linear constraints like $a^Tx\leq b$, and the symmetry detection routines needed here are already needed in MILP. Now extending symmetry detection to conic constraints, e.g., to a conic-quadratic constraint $x_0\geq \Vert x_{1:n}\Vert_2$, is relatively easy because one does not have to hassle with data, but only structure. Adding symmetry detection for possibly newly added cone types to a MICP solver is thus a small burden. And detecting and exploting symmetry in MICP can have a decisive effect. The following logs show MOSEK's solution paths to solve one of the aforementioned geometric facility location problems, with and without symmetry detection and handling, respectively.

Figure 3: Solving disk covering instances w/ and w/o symmetry detection


Tuesday, April 5, 2022

Easter 2022

Due to Easter support and sales are closed from Thursday, April 14th, until Monday, April 18th, inclusive.


The MOSEK team wishes everyone a peaceful Easter.

Friday, March 25, 2022

Improved performance of the interior-point optimizer when using an AMD CPU

One of the improvements in the recent released Mosek version 10 is better performance when run on a computer that has a recent AMD CPU. In order to illustrate that the table below is shown.

Problem 9.3 10.0
pds-100 93s 66s

The table shows the time taken in seconds to solve some well-known linear optimization problems on a AMD EPYC 7543 CPU from the Zen3 familie running the interior-point optimizer on 1 thread. On this AMD Zen3 family CPU Mosek version 10 is approximately 30% faster which is a significant improvement. It should be emphasized that on easier problems than pds-100 then the speed improvement is less than reported above. Nevertheless an upgrade to Mosek version 10 should be particularly worthwhile when using an AMD CPU.

Wednesday, March 23, 2022

MOSEK 10 Beta release

We are excited to announce the release of MOSEK 10 Beta. 

This version introduces many new features, in particular:

  • Support for Apple M1.
  • Improved control over multithreading.
  • Efficiency improvements in the interior-point and mixed-integer optimizers, improved tuning for various platforms.
  • New strategies in the mixed-integer optimizer.
  • Disjunctive constraints.
  • More convenient syntax for conic constraints in the Optimizer API.
  • And many more improvements.
To read more and try the new version see https://www.mosek.com/products/version-10/

In the coming weeks we will publish a series of posts highlighting selected new features of MOSEK 10.

Your feedback will be most appreciated.

The MOSEK team

Thursday, January 20, 2022

MIP 2022

Similarly to previous years MOSEK is proud to be one of the sponsors of MIP2022 - Mixed Integer Programming Workshop 2022, taking place May 23–26, 2022 at DIMACS, Rutgers University.

More details at https://www.mixedinteger.org/2022/

Monday, January 10, 2022

Planned end of support for version 8

On 31-may-2022 we will be stopping active support for version 8 which was released back in 2016.

For details of release and support policy see https://www.mosek.com/products/release-policy/

Tuesday, December 14, 2021

Log4j statement

Neither MOSEK nor any of the tools shipped with the MOSEK package make use of Log4j. The MOSEK library is not vulnerable to the Log4j exploit.