SO业务编排>> linprog2d>> 返回
项目作者： astoeckel

项目描述 ：
2D Linear Programming Solver for C/JS/Python
高级语言： C
项目地址: git://github.com/astoeckel/linprog2d.git
创建时间： 2018-05-25T03:09:56Z
项目社区：https://github.com/astoeckel/linprog2d
开源协议：GNU General Public License v3.0
下载


linprog2d ‒ Linear Programming Solver for 2D Problems

Build Status
Coverage Status

liblinprog2d is a small C library for solving two-dimensional linear programming problems in linear time (with respect to the number of constraints). The library can be compiled to JavaScript/WebAssembly and embedded in web applications (4.9kiB gzipped) or called from Python using the provided Python package.

Launch interactive demo.

The code is written in pure C89/C90 and has no dependencies aside from the standard-library functions sqrt(), fabs(), malloc(), and free() (heap allocations can be deactivated by defining LINPROG2D_NO_ALLOC). To prevent numerical instabilities, the code conditions the input problem (shifts the coordinate system, normalises the constraints) before solving. The library comes with an extensive test-suite (100% line coverage).

How to use

The library solves a two-dimensional programming problem of the form

  1.  minimize cx    * x + cy    * y ,
  2. such that Gx[i] * x + Gy[i] * y >= h[i] for all i ,

where cx, cy are constants defining the gradient of the minimization and Gx, Gy, h define a set of constraints. Goal is to find variables x and y which fulfill the above constraints.

Consider the following problem: maximize 5x + 10y such that the following constraints hold

  1.     x          >=   0,
  2.              y >=   0,
  3.     x          <   15,
  4. 8 * x +  8 * y <  160,
  5. 4 * x + 12 * y <  180

The following examples show how to solve this problem using linprog2d in C, JavaScript, and Python.

C

The following C code demonstrates how to use linprog2d to solve a simple problem:

  1. #include <linprog2d.h>
  2. #include <stdio.h>
  4. int main() {
  5.     const double Gx[5U] = {1.0, 0.0, -1.0, -8.0, -4.0};
  6.     const double Gy[5U] = {0.0, 1.0, 0.0, -8.0, -12.0};
  7.     const double h[5U] = {0.0, 0.0, -15.0, -160.0, -180.0};
  9.     const double cx = -5.0;
  10.     const double cy = -10.0;
  11.     linprog2d_result_t res =
  12.         linprog2d_solve_simple(cx, cy, Gx, Gy, h, 5U);
  14.     if (res.status == LP2D_POINT) {
  15.         printf("x=%0.2f y=%0.2f\n", res.x1, res.y1);
  16.         return 0;
  17.     }
  18.     printf("Problem is infeasible, unbounded, or not a single point.");
  19.     return 1;
  20. }

Note that linprog2d_solve_simple allocates memory for the solver, solves the problem, and frees the memory it allocated. If you want, linprog2d provides an API that allow to re-use the same memory for multiple problems, as well as functions that allow to perform manual memory management.

For more information on how to use the library, especially the heap-allocation free version of the library, consult the documentation in the header linprog2d.h.

JavaScript

The following code solves the same problem as the C code above, but uses the JavaScript/WebAssembly library located in the dist directoy of this repository (or build it yourself, see below):

  1. linprog2d.init().then((solve) => {
  2.     const Gx = [1.0, 0.0,  -1.0,   -8.0,   -4.0];
  3.     const Gy = [0.0, 1.0,   0.0,   -8.0,  -12.0];
  4.     const h  = [0.0, 0.0, -15.0, -160.0, -180.0];
  5.     const res = solve(-5.0, -10.0, Gx, Gy, h);
  6.     if (res.status == linprog2d.POINT) {
  7.         console.log('x =', res.x1, ' y = ', res.y1);
  8.     }
  9. });

Python

Make sure the liblinprog2d.so is in your library search path (either by setting the environment variable LD_LIBRARY_PATH accordingly or installing liblinprog2d.so to /usr/share/local/lib/). Install the linprog2d Python package by executing the following in the linprog2d directory:

  1. pip3 install .

You can use the library as follows:

  1. import linprog2d
  3. Gx = [1.0, 0.0,  -1.0,   -8.0,   -4.0];
  4. Gy = [0.0, 1.0,   0.0,   -8.0,  -12.0];
  5. h  = [0.0, 0.0, -15.0, -160.0, -180.0];
  6. res = linprog2d.solve(-5.0, -10.0, Gx, Gy, h)
  7. if res.status == linprog2d.POINT:
  8.     print("x =", res.x1, "y =", res.y1)

Performance

This library solely solves a special class linear-programming (LP) problems, namely those with only two variables. Correspondingly, it is considerably faster than general LP solvers such as cvxopt.

Performance comparison between cvxopt and linprog2d

The above image has been generated by the test_performance.py script located in the test folder. While the time required to solve a problems scales linearly with the number of constraints for both libraries (the dashed line is a linear fit), linprog2d is about 40 times faster than the general-purpose solver. In both cases this includes the overhead of the Python binding. Note that linprog2d has not been optimized for performance, but mainly for being (mostly) correct and easy to understand.

How to build

liblinprog2d is written in the C++-compatible subset of C89/C90. So all you need is a standards-compliant C or C++ compiler. Since liblinprog2d is just a single source file, building should be fairly straight forward on any platform; just compile linprog2d.c or test/test_linprog2d.c if you want to execute the unit tests.

Linux and other Unix-like operating systems

For your convenience, this repository comes with a Makefile that should work on most Unix-like platforms. To build and test liblinprog2d just execute the following on your command line:

  1. git clone https://github.com/astoeckel/linprog2d
  2. cd linprog2d
  3. make && make test

JavaScript/WebAssembly backend

Building the JavaScript/WebAssembly version is a little bit more complicated. You’ll need to install emsdk, as well as the npm package babel-minify. Make sure that the emsdk environment is active, then make the wasm target by executing the following in the linprog2d directory:

  1. make wasm

If you want to run the unit-tests in the JavaScript/WebAssembly version you’ll have to install nodejs. Execute the following command in the linprog2d directory

  1. emcc test/test_linprog2d.c && node ./a.out.js

References

The following references describe the algorithms used in this library in more detail. The original linear-time 2D linear-programming solver has been proposed by Nimrod Megiddo. It depends on an implementation of the median in linear-time, which is relalized in the code using the “Median-of-medians” selection algorithm proposed by Blum, Floyd, Pratt Rivest, Tarjan.

Primary resources

  • Nimrod Megiddo. (1983). Linear-Time Algorithms for Linear Programming in R³ and Related Problems. SIAM journal on computing, PDF
  • Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer and System Sciences. PDF

Secondary resources

  • Sariel Har-Peled. Two dimensional linear programming. Online
  • Russel Cohen. My Favorite Algorithm: Linear Time Median Finding. Online
  • Eduardo Sany Laber. Selection in Linear Time. Presentation, PDF

License

  1. linprog2d --- Two-dimensional linear programming solver
  2. Copyright (C) 2018 Andreas Stöckel
  4. This program is free software: you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation, either version 3 of the License, or
  7. (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12. GNU General Public License for more details.
  14. You should have received a copy of the GNU General Public License
  15. along with this program.  If not, see <https://www.gnu.org/licenses></https:>.