Improving Octave's linear and integer programming facility

maintainers
#1

I see that Octave uses GLPK for linear and integer programming. GLPK’s performance is terrible relative to other open source solvers, notably HiGHS. This is an MIT-licensed software system for solving linear programming problems (via simplex and barrier) and mixed-integer programming problems (via branch-and-cut). For example, HiGHS is significantly superior to the solvers in MATLAB for LP and, in particular, MIP.

HiGHS is looking to extend its user base, particularly in the context of other open-source mathematical software systems such as Octave. For example, we provide the LP and MIP solvers in SciPy.

If you’re interested in making use of HiGHS, please let me know

Julian Hall

2 Likes
Is there command to find kind of "prime factors" (that is different than actual prime factors) for any number?
#2

By all means, the more solver backends that Octave can use, the better. The best approach for LP, MILP and MINLP would be to enable multiple backends to be used with the same Octave frontend, analogous to how one can call different solvers from GAMS and AMPL with the same model. Matlab allows the same approach with its interior point methods and large / medium scale methods, so one can switch from one to another where possible. Switching solvers is a rational extension of that approach.

I am not familiar with the specific solver you mention but if you can use the linprog function from the optim package as a pattern for how the user can call it, it would be a very good start. The function uses this format:

 -- Function File: X = linprog (F, A, B)
 -- Function File: X = linprog (F, A, B, AEQ, BEQ)
 -- Function File: X = linprog (F, A, B, AEQ, BEQ, LB, UB)
 -- Function File: [X, FVAL] = linprog (...)

Also the bintprog function from Matlab isn’t implemented in Octave yet AFAIK. If your solver can do both linprog and bintprog it would solve two problems at once, since you mention both LP and MIP.

#3

Thanks for the suggestion @jajhall. The solver is

Looking at some independent benchmarks by Mittelmann (category Linear Programming)

Your solver seems indeed to be a better choice than GLPK and I am very interested, but time is always short and I cannot fully work on this promising project.

If you are familiar with Octave. What do you envision how should Octave users make use of HiGHS?

In general, one major step to become an happily embraced build dependency for Octave is to get packaged by major Linux distributions (e.g. Debian/Ubuntu, RedHat/Fedora). Do such packages exist? However, it is not impossible to have HiGHS as optional Octave build dependency.

#4

Using the linprog calling convention that you set out will require some interface code to be written, but it would be algorithmically trivial. As for discrete problems, Matlab’s current solver is intlinprog [bintprog is the special case of binary programming.] Once Octave can call HiGHS via linprog it’s a trivial extension to use HiGHS to solve MIPs using intlinprog calling conventions.

HiGHS does not yet solve nonlinear problems, so we can’t offer MINLP. However, the most popular optimization model is MIP

#5

HiGHS is not yet packaged by major Linux distributions, but it is something that will come in due course. I’ll look at what’s involved in getting this done but, if what @arungiridhar says is correct - that Octave has no MIP capability - then this is a major gap in your offering as it’s the most widely-used optimization problem class in Operations Research. Although GPLK has a MIP solver, it’s woefully poor compared with HiGHS on the basis of Mittelmann’s MILP benchmarks

#6

I myself have felt that pinch in MIPs and MILPs because of GLPK’s known performance characteristics. I have been converting my mixed integer problem instances into binary integer programs with integer coefficients, and then using Minisat to solve them (Minisat can only do 0/1 integer programming or plain SAT, but it does those well). That is, I have Octave functions for my own use to do the translation from a domain into Minisat’s languages, write the files, call Minisat, read its output, and translate back into the starting domain. In the sense that the time to translate one NP-complete problem instance into another is short compared to actually solving the NP-complete problem instance, this has been viable for me for many years, and is generally much faster than GLPK, but being able to call it natively from Octave without going through the file system would be a huge convenience.

I once looked into what it would take to link Minisat and Octave together but the codebases were very different, and it wasn’t clear how many Octave users needed MIP capability. But yes, if there exists an LP or MIP solver that outperforms GLPK and is license-compatible with Octave, I’m in favor of it.

1 Like
#7

It occurs to me that if you see benefits to not using linprog convention for example, you can present it with two different calling conventions. A good example of this is the fmincon function which is a wrapper to the nonlin_min function. The second is more powerful but the first provides Matlab compatibility. The end user can call either. In your case, one of the calling conventions could be the native HiGHS preferred way, and linprog and intlinprog and bintprog could all wrap that call.

2 Likes
#8

The native Highs API is radically different - and substantially more sophisticated due to the use that people make of LP and MIP solvers in optimization and operations research. However, we do have “single call” define-and-solve methods in the C and Python APIs, and they are comparable with the linprog/fmincon API

#9

Goodness, what a nightmare! I guess that one of the HiGHS team - with help from someone from Octave needs to look at the top level source code of linprog, and see what’s involved to call HiGHS rather than GLPK. Since HiGHS has a C API , and GLPK is written in C, it can’t be so hard. [Famous last words.]

#10

OK I can help you from the Octave end. With most Octave m-files of this nature, the m-file does the input validation and then calls a compiled function that does the heavy lifting.

Taking linprog as an example, you can see this line towards the end of the function:

  [x(1:nr_f, 1) fval(1, 1)] = glpk (f, [A; Aeq], [b; beq], lb, ub, ctype);

Everything before that line was input validation.

In principle, (and yes we need to verify that with reality), that single line can be replaced by a call to HiGHS using HiGHS’s preferred function format and that would be a change in the solver that is invisible to the end user. In practice there will be some diagnostics that will reveal what solver is being used.

Of course, if the preceding input validation doesn’t make sense for HiGHS, it would be better to write a separate m-file that calls HiGHS.

Can you provide the preferred function prototype for the HiGHS function to do linear programming? I can help with the m-file end.

Edit: to explain that line of code, it is calling a function called glpk and passing it all the constraint matrices and RHS values and all that good stuff. The glpk function is in this case another m-file (but it could have been compiled too if the linprog developer wanted) that does yet more input validation and then calls this compiled function:

  [xopt, fmin, errnum, extra] = ...
    __glpk__ (c, A, b, lb, ub, ctype, vartype, sense, param);

That __glpk__ function in turn is a compiled function that simply calls the GLPK API and returns the results. The linprog developer could have called __glpk__ directly if they didn’t need the second round of input validation that glpk.m was providing.

Similarly, let’s say we have a C++ function named __highs__ that calls the HiGHS API. That function __highs__ can be called by an m-file named say highs.m. In future, linprog.m can switch over to calling highs.m or even __highs__ instead of calling glpk.m like it is now.

Next steps for you: create a C++ function called __highs__ and make it call the HiGHS API.

@siko1056, do you think this should be a DLD oct file like glpk or is there a better approach? Will this be an external package like optim or will it be a DLD in core like glpk and Qhull functions?

Edit 2: @jajhall if you want to see an example of a C++ function that calls a private library API, there are several examples in octave: 439eb9bd4c04 /libinterp/dldfcn/ but see the smaller ones first before you see __glpk__.cc. Also, don’t worry about the stuff like Octave namespaces yet. If you write a C++ function to call the HiGHS API we can build from there.

#11

Thanks. I’ve looked at
octave: 439eb9bd4c04 /libinterp/dldfcn/glpk.cc
and I could certainly write an equivalent C++ file to give the same functionality by calling methods from the Highs class. However, I’d need to be able to run test instances to debug it. If I couldn’t run it in something like VScode, I’d have to put in print statements to identify behaviour. I guess that you must have some sort of set-up that allows development in this manner. Since HiGHS is written in C++, and GLPK in C, I guess that all the things like double *c = C.fortran_vec (); will not be necessary.

Given the right development environment, I don’t think this will take long

#12

It is possible to add unit tests using a syntax that will look like a comment to the C++ parser but which will be read by the Octave testing mechanism and executed. Typically those lines begin with “%!” symbols. See the other files in the directory for examples. You would make Octave aware of the new function by adding a line to octave: 439eb9bd4c04 libinterp/dldfcn/module-files

The Octave naming convention is to use the two leading and trailing underscores for private internal functions and to use plain names for functions that might be called by the end user. If you already have input validation code in C++ from other projects, the function you’re writing could even be called directly by the end user without having to go through an m-file, at your discretion.

#13

I don’t know if anyone is using VSCode for Octave development. But it’s probably possible to use it.
Please, note that Octave uses an autotools build chain. I’m not sure if it will be possible to combine that with MSVC. (But it might…)

Since you are using VSCode, I’m assuming you are on a Windows system. Is that right?
In that case, please see the following Wiki page for possible development options that have been tested on that platform:
Building on Microsoft Windows - Octave

That’s most probably not a comprehensive list though…

1 Like
#14

So, would I build Octave from source “The right way” (according to Octave for Debian systems - Octave), ie via Building - Octave and then have octave: 439eb9bd4c04 libinterp/dldfcn/module-files to edit locally?

I’d also have to get Octave to link to the HiGHS library. Perhaps it’s simple to see where to insert this into a make file.

HiGHS has no dependencies

#15

No, I’m developing on Linux. It sounds as if the route to using VSCode is going to be hard. I’m OK using print statements. After all, I’m only debugging a single interface method, not the optimization solvers themselves.

#16

IIUC, you are planning to implement a new dld library that interfaces to the HiGHS library? In that case, it sounds like a reasonable approach to add a new file for that interface and add a new line to that file to have it be included in the build system.

IIUC, your plan is to implement the HiGHS interface in a dld library. In that case, you won’t need to link Octave to the HiGHS library. It should be sufficient to add the necessary CPPFLAGS, LDFLAGS and LIBS to the libinterp/dldfcn/module-files file.
In a first step to get started, you could add those flags literally to match what you need on your platform.
In some later step, configure tests should be added to get the correct flags. I might be able to help with that. (I don’t know anything about the HiGHS library though…)

2 Likes
#17

Can you confirm that the first thing I should do is to build Octave from source?

What’s a “dld” library?

The natural HiGHS libraries on Linux are shared. Does Octave need static libraries? I can get static libraries for HiGHS, but I’m less familiar with working with them.

#18

I should add that, although HiGHS has extensive input validation code in C++, this is only for sparse matrices. Since I see that you allow rectangular (dense) definition of matrices, I’ll leave the input validation to Octave.

#19

:+1:

The files in the folder libinterp/dldfun are compiled into shared libraries.

Shared libraries are fine.

2 Likes
#20

Thanks. I now feel that I can start doing something. I’ll let you know how I get on!

1 Like