Improving Octave's linear and integer programming facility

I’ve got Octave installed, and used it to solve a trivial LP.

I’ve added a HiGHS line to module-files, created __highs__.cc (as a chopped down copy of __glpk__.cc, with the “top” methods name changed from glpk to highs). Everything compiles and links OK.
Only odd thing is that the command
[xopt, f] = glpk(c, A, b)
now runs HiGHS, rather than GLPK. Not a problem for me, of course!

__highs__.cc doesn’t do anything yet, or even include Highs.h. Baby steps…

I’m keeping track of changes I make on GitHub - jajhall/octave: Octave for HiGHS

1 Like

I’ve written __highs__.cc and Octave will now solve LPs and MIPs using HiGHS.

  • I’ve not tested the use of the params structure
  • Octave is not picking up the HiGHS libraries: I have to run it as
    LD_LIBRARY_PATH=/home/jajhall/HiGHS/build/lib .build/run-octave
1 Like

You might get around setting LD_LIBRARY_PATH by adding -rpath flags to the LDFLAGS of the __highs__ library.
But that’s not really necessary to move this forward. Might just be a convenience for your tests.

As the next steps, you could try to move that towards a changeset of the Octave repository. If you prefer working with Git/GitHub, you could fork our (read-only) mirror on there and make your changes on a new branch based on the default branch.
Additionally, we’d need configure checks for the HiGHS library. I didn’t find HiGHS when I searched for it in the (default) apt packages for Ubuntu 21.10. Could you please give instructions how to install it on that distribution?

Is HiGHS even packaged for any distribution? Maybe it would make more sense to have this as part of an Octave package or as its own Octave package…

I’m wary of messing with the HiGHS (CMake) build, as I didn’t write it. Indeed, I’m not a computer scientist, so some of what “just worked” yesterday was a bit scary - but very satisfying! The rest of the HiGHS team (of 3-4) are all young people with CS in their background.

I’m confident enough to fork your repository, and will merge my changes into a branch.

HiGHS isn’t packaged for any distribution, but it’s another thing that we’ll do in time. If I understand correctly what you’re after, the download and build instructions for Linux are HiGHS - High-performance parallel linear optimization software Note that the HiGHS repository has CI tests for builds with different compilers on Windows, Linux and MacOS, and is also built as binaries by the JuMP people for many more architectures on these OS, so it’s robust in this way.

If you want HiGHS sooner rather than later, then it sounds as if it’s better to have it as “part of an Octave package or as its own Octave package”, rather than wait until we’ve got it packaged for Linux distributions.

In getting __highs__.cc written, using a copy of glpk.m, I’ve matched the scalar parameter and return values as best I can - with reference to Linear Programming (GNU Octave (version 6.4.0)). However, they are (naturally) very much tied to GLPK. There are control parameters and return errnum values for which there are no HiGHS equivalents - the latter being because HiGHS is more robust.

So, I propose to write a specific highs.m, for which a “HiGHS” section of the “Linear Programming” documentation would be required.

In passing, I note that the “Linear Programming” section of your documentation should really be “Linear and Integer Programming”, otherwise people will not know that you have an integer programming solver. I also observe that “6 (GLP_UNBND) Problem has no unbounded solution.” should read “6 (GLP_UNBND) Problem is unbounded” or, if you want to refer to a “solution”, say “Problem has no bounded solution”

The “problem” I’m seeing with adding the HiGHS interface to Octave core at this point in time is that those versions of Octave that are most likely used “in the wild” (i.e., those packaged by distributors like Debian, Ubuntu, Fedora, …) won’t be compiled with that interface. “Normal” end-users wouldn’t get to use the new interface with those versions of Octave. They would need to re-compile all of Octave after installing all of its many dependencies (now including “HiGHS”). As you probably noticed, that’s quite some task for someone who “just” would like to use Octave.

If that interface would be part of an Octave package, it would be much easier for an end-user to get to appreciate it. They would “just” need to compile the HiGHS library themselves, set the necessary environment variables (depending on where they installed the library), and execute something like pkg install highs-1.0.tar.gz after they downloaded the package.

You could still use the __highs__.cc and highs.m you already wrote basically without any extra changes for that new potential package.

I’m not saying that that interface can never make it into Octave core. But maybe it might make more sense to first have an Octave package, and decide later on whether it should be merged to Octave core…

1 Like

Thanks for the back-story, let’s aim for an Octave package for now. In due course it may make sense for Octave to ditch GLPK all together. I note that GLPK’s not ben updated in 2 years so, as well as being inferior to HiGHS, maybe support isn’t what it was.

Looking forward, I note that Octave has a (convex) Quadratic Programming solver. So does HiGHS, but it’s not as well developed as the LP and MIP solvers. That said, it might still be worth offering it as an alternative to your incumbent solver. I guess that this could be best achieved by allowing users to include a “Q” parameter in the call to highs from Octave. Users will have to be warned that they can’t combine non-zero Q with non-continuous vartype settings. HiGHS won’t be able to solve MIQPs for a while!

1 Like

Checking in. Would you have a preliminary version of the LP function available for download?

Yes, it’s available within

Note that octave is not picking up the HiGHS libraries: I have to run it as

LD_LIBRARY_PATH=/home/jajhall/HiGHS/build/lib .build/run-octave

However, I don’t imagine that fixing this is hard for someone with good knowledge of Octave

1 Like

IIUC, that’s not specific to Octave.
You could probably add a corresponding -rpath argument to the linker flags to have the your .oct file library search that directory on runtime without setting LD_LIBRARY_PATH explicitly.

Anyway, I’d really recommend to convert that to an Octave package if you’d like that others will be able to use this function.
Packaging the two files from Added highs.cc highs.m and modified module-files · jajhall/octave-1@d50d084 (github.com) would probably be enough…

I’m sure you’ll get help here if you have specific questions on how to create an Octave package.

Edit: For a basic introduction to creating Octave package, see the manual:
Creating Packages (GNU Octave (version 6.4.0))

1 Like

Thanks. I’m going to extend highs.m and highs.cc so that they can handle QP problems, and bring in the PhD student of mine (Michael Feldmeier) who wrote our QP solver to see how his solver compares with what you’ve got at present.

Hi @jajhall, could you clarify whether HiGHS can handle matrices larger than 2^32 elements if required? GLPK has a known size limit because it uses 32-bit integers internally for indexing.

HiGHS can be compiled so that all integers are 64 bits, allowing it to handle LPs with more than 2^32 entries. However, any such problem would be computationally very expensive to solve, unless it was reduced significantly by presolve. Even if GLPK were compiled with 64-bit integers, the computational cost of using GLPK to solve LPs with so many nonzeros would almost certainly be prohibitive.

In passing, we’ve not forgotten about Octave, and will work further on the interface once HiGHS can be packaged for Linux distributions. We anticipate that this will be possible on a timescale of months.

2 Likes

Looking forward to seeing HiGHS as both a Linux package and and Octave package!