Linear Programmnig (LP)¶
minimize c^T x + C
s.t. Gx <= h
Ax == b
lb <= x <= ub
x_i is integer or continuous variablce
This optimization problem is called Linear Programming (LP) Problem. For example, the following problem is one of the LP.
from flopt import Variable, Problem
# variables
a = Variable(name="a", lowBound=0, upBound=1, cat="Integer")
b = Variable(name="b", lowBound=1, upBound=2, cat="Continuous")
c = Variable(name="c", lowBound=1, upBound=3, cat="Continuous")
# problem
prob = Problem(name="LP")
prob += a + b + c + 2
prob += a + b == 2
prob += b - c <= 3
print(prob)
>>> Name: None
>>> Type : Problem
>>> sense : minimize
>>> objective : a+b+c+2
>>> #constraints : 2
>>> #variables : 3 (Continuous 2, Integer 1)
flopt to LP¶
We can convert this into Lp form as follows.
from flopt.convert import LpStructure
lp = LpStructure.fromFlopt(prob)
To show the contents of lp,
print(lp.show())
>>> LpStructure
>>> obj c.T.dot(x) + C
>>> s.t. Gx <= h
>>> Ax == b
>>> lb <= x <= ub
>>> #x
>>> 3
>>> c
>>> [1. 1. 1.]
>>> C
>>> 2
>>> G
>>> [[ 0. 1. -1.]]
>>> h
>>> [3.]
>>> A
>>> [[1. 1. 0.]]
>>> b
>>> [2.]
>>> lb
>>> [0. 1. 1.]
>>> ub
>>> [1. 2. 3.]
>>> x
>>> [Variable("a", 0, 1, "Integer", 0) Variable("b", 1, 2, "Continuous", 1.5)
>>> Variable("c", 1, 3, "Continuous", 2.0)]
Formulation with only equal constraints¶
You can obtain the formulaton with only eqaual constraints by .toAllEq()
minimize c^T x + C
s.t. Ax == b
lb <= x <= ub
x_i is integer or continuous variablce
print(lp.toAllEq())
>>> LpStructure
>>> #x 4
>>> #c (4,)
>>> #C 2
>>> #G None (0-element None %)
>>> #h None
>>> #A (2, 4) (0-element 37.500 %)
>>> #b (2,)
>>> #lb 4
>>> #ub 4
To make the formulation easier to read, we show it in the form of flopt.
print(lp.toAllEq().toFlopt().show())
>>> Name: None
>>> Type : Problem
>>> sense : minimize
>>> objective : a+b+c+2
>>> #constraints : 2
>>> #variables : 4 (Continuous 3, Integer 1)
>>>
>>> C 0, name None, a+b-2.0 == 0
>>> C 1, name None, b-c+__s_0-3.0 == 0
__s_0 is a slack variable for an equal constraint.
Formulation with only non-equal constraints¶
You can obtain the formulaton with only non-eqaual constraints by .toAllNeq()
minimize c^T x + C
s.t. Gx <= h
lb <= x <= ub
x_i is integer or continuous variablce
print(lp.toAllNeq())
>>> LpStructure
>>> #x 3
>>> #c (3,)
>>> #C 2
>>> #G (3, 3) (0-element 33.333 %)
>>> #h (3,)
>>> #A None (0-element None %)
>>> #b None
>>> #lb 3
>>> #ub 3
To make the formulation easier to read, we show it in the form of flopt.
print(lp.toAllNeq().toFlopt().show())
>>> Name: None
>>> Type : Problem
>>> sense : minimize
>>> objective : a+b+c+2
>>> #constraints : 3
>>> #variables : 3 (Continuous 2, Integer 1)
>>>
>>> C 0, name None, b-c-3.0 <= 0
>>> C 1, name None, a+b-2.0 <= 0
>>> C 2, name None, -a-b+2.0 <= 0
LP to flopt¶
# make Lp model
c = [1, 1, 1]
C = 2
A = [[1, 0, 1],
[1, -1, 0]]
b = [2, 3]
lb = [1, 1, 0]
ub = [2, 3, 1]
types=["Binary", "Continuous", "Continuous"]
from flopt.convert import LpStructure
prob = LpStructure(c, C, A=A, b=b, lb=lb, ub=ub, types=types).toFlopt()
prob.show()
>>> Name: None
>>> Type : Problem
>>> sense : minimize
>>> objective : x_0+x_1+x_2+2
>>> #constraints : 2
>>> #variables : 3 (Continuous 2, Binary 1)
>>>
>>> C 0, name None, x_0+x_2-2.0 == 0
>>> C 1, name None, x_0-x_1-3.0 == 0