Coverage for lpsolvers / cdd_.py: 88%

1#!/usr/bin/env python 

2# -*- coding: utf-8 -*- 

3# 

4# SPDX-License-Identifier: LGPL-3.0-or-later 

5# Copyright (C) 2016-2022 Stéphane Caron 

6 

7"""Solver interface for cdd.""" 

8 

9from typing import Optional 

10 

11import cdd 

12import numpy as np 

13 

14 

15def cdd_solve_lp( 

16 c: np.ndarray, 

17 G: np.ndarray, 

18 h: np.ndarray, 

19 A: Optional[np.ndarray] = None, 

20 b: Optional[np.ndarray] = None, 

21) -> np.ndarray: 

22 r"""Solve a linear program using the LP solver from cdd. 

23 

24 The linear program is defined by: 

25 

26 .. math:: 

27 

28 \\begin{split}\\begin{array}{ll} 

29 \\mbox{minimize} & 

30 c^T x \\\\ 

31 \\mbox{subject to} 

32 & G x \\leq h \\\\ 

33 & A x = b 

34 \\end{array}\\end{split} 

35 

36 It is solved using `cdd <https://github.com/mcmtroffaes/pycddlib>`_. 

37 

38 Parameters 

39 ---------- 

40 c : 

41 Linear cost vector. 

42 G : 

43 Linear inequality constraint matrix. 

44 h : 

45 Linear inequality constraint vector. 

46 A : 

47 Linear equality constraint matrix. 

48 b : 

49 Linear equality constraint vector. 

50 solver : 

51 Solver to use, default is GLPK if available 

52 

53 Returns 

54 ------- 

55 : 

56 Optimal (primal) solution of the linear program, if it exists. 

57 

58 Raises 

59 ------ 

60 ValueError 

61 If the linear program is not feasible. 

62 """ 

63 if A is not None and b is not None: 

64 v = np.hstack([h, b, -b]) 

65 U = np.vstack([G, A, -A]) 

66 else: # no equality constraint 

67 v = h 

68 U = G 

69 v = v.reshape((v.shape[0], 1)) 

70 constraints = np.hstack([v, -U]) 

71 objective = np.hstack([[0.0], c]) 

72 lp = cdd.linprog_from_array( 

73 np.vstack([constraints, objective]), # type: ignore 

74 obj_type=cdd.LPObjType.MIN, 

75 ) 

76 cdd.linprog_solve(lp) 

77 if lp.status != cdd.LPStatusType.OPTIMAL: 

78 raise ValueError(f"Linear program not feasible: {lp.status}") 

79 return np.array(lp.primal_solution)