In pulp’s documentation https://coin-or.github.io/pulp/guides/how_to_debug.html, it says that
Check the precision of the numbers. If you have very big numbers (with a high precision), this generally causes problems with solvers. For example, never use a parameter that is 100000000000 inside your problem.
The problem is that my LP has parameters this large. Is there some transformation I can do to the problem that will help? I tried scaling the parameters by dividing all by the same large number, but then I end up with very small decimal values for some of the parameters as only the right side of each equation/inequality is large. An example constraint is 3*x + 4*y == 10000000000 where x and y must be integers.
Here is a more complete set of my code
<code>f = open('datainput13_test.txt', 'r')
lines = f.readlines()
cost = 0
for i in range(0, len(lines), 4):
a_coeff_eq_1 = int(lines[i].split(':')[1].split(',')[0].split('+')[1])
a_coeff_eq_2 = int(lines[i].split(':')[1].split(',')[1].split('+')[1])
b_coeff_eq_1 = int(lines[i+1].split(':')[1].split(',')[0].split('+')[1])
b_coeff_eq_2 = int(lines[i+1].split(':')[1].split(',')[1].split('+')[1])
c_eq_1 = int(lines[i+2].split(':')[1].split(',')[0].split('=')[1]) + 10000000000000
c_eq_2 = int(lines[i+2].split(':')[1].split(',')[1].split('=')[1]) + 10000000000000
a_coeff_eq_1
a_coeff_eq_2
b_coeff_eq_1
b_coeff_eq_2
c_eq_1
c_eq_2
prob = LpProblem("MyProb", LpMinimize)
a = LpVariable("a", 0, None, LpInteger)
b = LpVariable("b", 0, None, LpInteger)
prob += a_coeff_eq_1 * a + b_coeff_eq_1 * b == c_eq_1
prob += a_coeff_eq_2 * a + b_coeff_eq_2 * b == c_eq_2
prob += 3*a + b
prob.solve(PULP_CBC_CMD(msg=1))
if LpStatus[prob.status] == 'Optimal':
for v in prob.variables():
if v.name == 'a':
cost += 3*v.varValue
elif v.name == 'b':
cost += v.varValue
print(v.name, "=", v.varValue)
print(cost)
</code>
<code>f = open('datainput13_test.txt', 'r')
lines = f.readlines()
cost = 0
for i in range(0, len(lines), 4):
a_coeff_eq_1 = int(lines[i].split(':')[1].split(',')[0].split('+')[1])
a_coeff_eq_2 = int(lines[i].split(':')[1].split(',')[1].split('+')[1])
b_coeff_eq_1 = int(lines[i+1].split(':')[1].split(',')[0].split('+')[1])
b_coeff_eq_2 = int(lines[i+1].split(':')[1].split(',')[1].split('+')[1])
c_eq_1 = int(lines[i+2].split(':')[1].split(',')[0].split('=')[1]) + 10000000000000
c_eq_2 = int(lines[i+2].split(':')[1].split(',')[1].split('=')[1]) + 10000000000000
a_coeff_eq_1
a_coeff_eq_2
b_coeff_eq_1
b_coeff_eq_2
c_eq_1
c_eq_2
prob = LpProblem("MyProb", LpMinimize)
a = LpVariable("a", 0, None, LpInteger)
b = LpVariable("b", 0, None, LpInteger)
prob += a_coeff_eq_1 * a + b_coeff_eq_1 * b == c_eq_1
prob += a_coeff_eq_2 * a + b_coeff_eq_2 * b == c_eq_2
prob += 3*a + b
prob.solve(PULP_CBC_CMD(msg=1))
if LpStatus[prob.status] == 'Optimal':
for v in prob.variables():
if v.name == 'a':
cost += 3*v.varValue
elif v.name == 'b':
cost += v.varValue
print(v.name, "=", v.varValue)
print(cost)
</code>
f = open('datainput13_test.txt', 'r')
lines = f.readlines()
cost = 0
for i in range(0, len(lines), 4):
a_coeff_eq_1 = int(lines[i].split(':')[1].split(',')[0].split('+')[1])
a_coeff_eq_2 = int(lines[i].split(':')[1].split(',')[1].split('+')[1])
b_coeff_eq_1 = int(lines[i+1].split(':')[1].split(',')[0].split('+')[1])
b_coeff_eq_2 = int(lines[i+1].split(':')[1].split(',')[1].split('+')[1])
c_eq_1 = int(lines[i+2].split(':')[1].split(',')[0].split('=')[1]) + 10000000000000
c_eq_2 = int(lines[i+2].split(':')[1].split(',')[1].split('=')[1]) + 10000000000000
a_coeff_eq_1
a_coeff_eq_2
b_coeff_eq_1
b_coeff_eq_2
c_eq_1
c_eq_2
prob = LpProblem("MyProb", LpMinimize)
a = LpVariable("a", 0, None, LpInteger)
b = LpVariable("b", 0, None, LpInteger)
prob += a_coeff_eq_1 * a + b_coeff_eq_1 * b == c_eq_1
prob += a_coeff_eq_2 * a + b_coeff_eq_2 * b == c_eq_2
prob += 3*a + b
prob.solve(PULP_CBC_CMD(msg=1))
if LpStatus[prob.status] == 'Optimal':
for v in prob.variables():
if v.name == 'a':
cost += 3*v.varValue
elif v.name == 'b':
cost += v.varValue
print(v.name, "=", v.varValue)
print(cost)
The coefficients on a and b can be quite small compared to the cs.
Sample from input file
<code>Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706
</code>
<code>Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706
</code>
Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706
10
This problem has a single analytic integer solution that has nothing to do with linear programming:
<code>import io
import re
import typing
DELTA = int(1e13)
class Params(typing.NamedTuple):
a1: int
a2: int
b1: int
b2: int
c1: int
c2: int
@classmethod
def from_match(cls, match: re.Match) -> typing.Self:
return cls(
a1=int(match['a1']),
a2=int(match['a2']),
b1=int(match['b1']),
b2=int(match['b2']),
c1=int(match['c1']),
c2=int(match['c2']),
)
def solve(self) -> tuple[
int, # x
int, # y
int, # offset
]:
a1, a2, b1, b2, c1, c2 = self
xoff = (
(
DELTA*(a1 + b1 - a2 - b2) # this is zero!
+ c2*(a1 + b1) - c1*(a2 + b2)
)//(
b2*(a1 + b1) - b1*(a2 + b2)
)
)
x = (c1 - b1*xoff + DELTA)//(a1 + b1)
y = x + xoff
return x, y, xoff
def errors(self, x: int, y: int) -> tuple[int, int]:
a1, a2, b1, b2, c1, c2 = self
return (
a1*x + b1*y - c1 - DELTA,
a2*x + b2*y - c2 - DELTA,
)
param_pat = re.compile(r'''(?ix)
Button A: # first line
X(?P<a1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<a2> # named capture group
[+-][0-9]+ # integer with explicit sign
)s* # newline
Button B: # second line
X(?P<b1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<b2> # named capture grooup
[+-][0-9]+ # integer with explicit sign
)s* # newline
Prize: # third line
X=(?P<c1> # named capture group
[0-9]+ # integer without sign
), # intermediate space
Y=(?P<c2> # named capture group
[0-9]+ # integer without sign
)
''')
def parse_all(f: typing.TextIO) -> typing.Iterator[Params]:
return map(Params.from_match, param_pat.finditer(f.read()))
def main() -> None:
with io.StringIO('''
Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706''') as f:
param, = parse_all(f)
print('For single sample input of')
print(param)
x, y, xoff = param.solve()
print('y - x =', xoff)
print(f'x = {x:,}')
print(f'y = {y:,}')
print('errors:', param.errors(x, y))
if __name__ == '__main__':
main()
</code>
<code>import io
import re
import typing
DELTA = int(1e13)
class Params(typing.NamedTuple):
a1: int
a2: int
b1: int
b2: int
c1: int
c2: int
@classmethod
def from_match(cls, match: re.Match) -> typing.Self:
return cls(
a1=int(match['a1']),
a2=int(match['a2']),
b1=int(match['b1']),
b2=int(match['b2']),
c1=int(match['c1']),
c2=int(match['c2']),
)
def solve(self) -> tuple[
int, # x
int, # y
int, # offset
]:
a1, a2, b1, b2, c1, c2 = self
xoff = (
(
DELTA*(a1 + b1 - a2 - b2) # this is zero!
+ c2*(a1 + b1) - c1*(a2 + b2)
)//(
b2*(a1 + b1) - b1*(a2 + b2)
)
)
x = (c1 - b1*xoff + DELTA)//(a1 + b1)
y = x + xoff
return x, y, xoff
def errors(self, x: int, y: int) -> tuple[int, int]:
a1, a2, b1, b2, c1, c2 = self
return (
a1*x + b1*y - c1 - DELTA,
a2*x + b2*y - c2 - DELTA,
)
param_pat = re.compile(r'''(?ix)
Button A: # first line
X(?P<a1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<a2> # named capture group
[+-][0-9]+ # integer with explicit sign
)s* # newline
Button B: # second line
X(?P<b1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<b2> # named capture grooup
[+-][0-9]+ # integer with explicit sign
)s* # newline
Prize: # third line
X=(?P<c1> # named capture group
[0-9]+ # integer without sign
), # intermediate space
Y=(?P<c2> # named capture group
[0-9]+ # integer without sign
)
''')
def parse_all(f: typing.TextIO) -> typing.Iterator[Params]:
return map(Params.from_match, param_pat.finditer(f.read()))
def main() -> None:
with io.StringIO('''
Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706''') as f:
param, = parse_all(f)
print('For single sample input of')
print(param)
x, y, xoff = param.solve()
print('y - x =', xoff)
print(f'x = {x:,}')
print(f'y = {y:,}')
print('errors:', param.errors(x, y))
if __name__ == '__main__':
main()
</code>
import io
import re
import typing
DELTA = int(1e13)
class Params(typing.NamedTuple):
a1: int
a2: int
b1: int
b2: int
c1: int
c2: int
@classmethod
def from_match(cls, match: re.Match) -> typing.Self:
return cls(
a1=int(match['a1']),
a2=int(match['a2']),
b1=int(match['b1']),
b2=int(match['b2']),
c1=int(match['c1']),
c2=int(match['c2']),
)
def solve(self) -> tuple[
int, # x
int, # y
int, # offset
]:
a1, a2, b1, b2, c1, c2 = self
xoff = (
(
DELTA*(a1 + b1 - a2 - b2) # this is zero!
+ c2*(a1 + b1) - c1*(a2 + b2)
)//(
b2*(a1 + b1) - b1*(a2 + b2)
)
)
x = (c1 - b1*xoff + DELTA)//(a1 + b1)
y = x + xoff
return x, y, xoff
def errors(self, x: int, y: int) -> tuple[int, int]:
a1, a2, b1, b2, c1, c2 = self
return (
a1*x + b1*y - c1 - DELTA,
a2*x + b2*y - c2 - DELTA,
)
param_pat = re.compile(r'''(?ix)
Button A: # first line
X(?P<a1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<a2> # named capture group
[+-][0-9]+ # integer with explicit sign
)s* # newline
Button B: # second line
X(?P<b1> # named capture group
[+-][0-9]+ # integer with explicit sign
), # intermediate space
Y(?P<b2> # named capture grooup
[+-][0-9]+ # integer with explicit sign
)s* # newline
Prize: # third line
X=(?P<c1> # named capture group
[0-9]+ # integer without sign
), # intermediate space
Y=(?P<c2> # named capture group
[0-9]+ # integer without sign
)
''')
def parse_all(f: typing.TextIO) -> typing.Iterator[Params]:
return map(Params.from_match, param_pat.finditer(f.read()))
def main() -> None:
with io.StringIO('''
Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706''') as f:
param, = parse_all(f)
print('For single sample input of')
print(param)
x, y, xoff = param.solve()
print('y - x =', xoff)
print(f'x = {x:,}')
print(f'y = {y:,}')
print('errors:', param.errors(x, y))
if __name__ == '__main__':
main()
<code>For single sample input of
Params(a1=51, a2=11, b1=38, b2=78, c1=16146, c2=3706)
y - x = -311
x = 112,359,550,876
y = 112,359,550,565
errors: (0, 0)
</code>
<code>For single sample input of
Params(a1=51, a2=11, b1=38, b2=78, c1=16146, c2=3706)
y - x = -311
x = 112,359,550,876
y = 112,359,550,565
errors: (0, 0)
</code>
For single sample input of
Params(a1=51, a2=11, b1=38, b2=78, c1=16146, c2=3706)
y - x = -311
x = 112,359,550,876
y = 112,359,550,565
errors: (0, 0)