"A factorisation-based regularised interior point method using the augmented system"

The implementation of the algorithm described in the paper can be found in the HiGHS repository, in the folder highs/ipm/hipo/.
To run the numerical experiments described in the paper, follow the instructions below.
Given that the solvers in HiGHS are continuously evolving, and that the performance is highly dependant on the machine used, the results may not match exactly the ones presented in the paper. However, they should be very close.

• Build HiGHS 1.12:

  • Download and install METIS 5.2.1

    git clone git@github.com:galabovaa/METIS.git
    cd METIS
    git checkout 521-ts
    cmake -S . -B build -DGKLIB_PATH=GKlib -DCMAKE_INSTALL_PREFIX=/installation/directory/
    cmake --build build
    cmake --install build
    cd ..
    

  • Install a BLAS library following the instructions at https://ergo-code.github.io/HiGHS/stable/installation/#BLAS
    Notice that the BLAS reference implementation, shipped with some Linux distributions, is not suitable to obtain high performance. We recommend installing OpenBLAS instead.

  • Download and build HiGHS 1.12

    git clone git@github.com:ERGO-Code/HiGHS.git
    cd HiGHS
    cmake -S . -B build -DHIPO=ON -DMETIS_ROOT=/installation/directory/
    cmake --build build
    cd ..
    

    Notice that you don't need to install HiGHS on your machine. Notice also that the version of METIS recommended in the official HiGHS installation instructions is different from the one recommended in the instructions above. Please, use the one recommended here.

• In Makefile, edit highs_path with the path to the HiGHS directory.

• The Netlib and PyPSA collections of problems are provided within this repository.
  The Mittelmann collection of problems is too large to be included here, but can be downloaded from the links at https://plato.asu.edu/ftp/lpfeas.html
  Put the downloaded mps files in the folder mittelman_pb/data.

• To compile the script, type make. This produces the executable run.

• To run a particular solver on a particular collection of problems, use

  ./run collection solver
  

  • collection can be netlib, pypsa, mittelmann.
  • solver can be hipo, ipx, simplex.
  • You can pass a third option to the executable, indicating which linear system to use for HiPO. This can be AS for augmented system or NE for normal equations. If it not specified, an automatic selection is performed. If the solver is not hipo, the option is ignored.
    For example, ./run netlib ipx runs the entire Netlib collection using the solver IPX; ./run pypsa hipo NE runs the entire PyPSA collection with the solver HiPO using the normal equations approach.
    The results are saved in a file named results_collection_solver_system.txt.

• Specific HiGHS options can be set within the function runHighs in the file RunHighs.cpp. They are already set to the options used in the paper.

• Once multiple solvers have been run on a given collection, use the Matlab script display_results.m to visualise the results. To do so, the variable collection should contain the name of the collection of problems. The variable solvers should contain pairs [solver system], where system is AS or NE. If solver is not hipo, or if the automatic selection of the system was used, any string can be used for system.
  The script produces a file table_collection.tex containing a table similar to the ones in the paper, that can be compiled into a PDF using a latex engine. The script also produces a logarithmic plot of the computational times, with an indication of the measured computational complexity.

For example, Table 2 and Figure 5 of the paper can be produced as follows:

• Run

  make
  ./run pypsa hipo NE
  ./run pypsa hipo AS
  ./run pypsa ipx
  ./run pypsa simplex
  

• In display_results.m, set collection = "pypsa";.
• In display_results.m, set solvers = ["hipo" "NE"; "hipo" "AS"; "ipx" "any string"; "simplex" "any string"];
• Run the Matlab script display_results.m. This will generate a file table_pypsa.tex containing the table and the figure will appear as a Matlab figure.