ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 27 Jul 2019 17:36:16 -0500Extremal Rays of a Conehttp://ask.sagemath.org/question/47275/extremal-rays-of-a-cone/Can I use Sage to compute the subspace of a vector space that lies in non-negative real Euclidean space?
For example,
If I compute the nullspace of the matrix,
A =
[ [ 1 0 0 -1 0]
[-1 1 0 0 1]
[ 0 -1 1 0 0]
[ 0 0 -1 1 -1] ]
I get,
[1,1,1,1,0],[0,−1,−1,0,1]
as basis. Now I would like to restrict the solution space to only vectors with non-negative entries. I believe the two basis vectors I am looking for are,
[1,1,1,1,0],[1,0,0,1,1].
My program is written in Python, but I am not sure there is anything written for this sort of problem. Using the simplex method of linear programming (objective function set to zero) only spits out a single solution vector which seems to be the sum of the two I want. I ask here because I see some classes for cones and methods that gives the extremal rays, but it seems I already have to know the extremal rays to use that class.ElGalloNegroSat, 27 Jul 2019 17:36:16 -0500http://ask.sagemath.org/question/47275/Is there a way to temporarily turn off sage's type checking?http://ask.sagemath.org/question/47227/is-there-a-way-to-temporarily-turn-off-sages-type-checking/ I'm having some difficulties writing sage code to solve linear programming problems using "natural variables", by substituting for them the variables required for MixedIntegerLinearProgram.
The code for "minimize_desired" is what I'd like to do, but it fails during the substitution with the error message "TypeError: no canonical coercion from Linear functions over Real Double Field to Symbolic Ring". What I'd like is for sage to just do the substitution and ignore the lack of coercion.
The code for "minimize_works" works, but I got past the type checking by changing everything to strings and then back into a sage object, which feels like a terrible kludge. However this does illustrate that, despite sage's worries about coercion, everything ends up fine for MixedIntegerLinearProgram.
Is there a way to turn off sage's type checking and just do the substitution?
Thanks,
Mike
Note: I simplified the examples below by eliminating all the code that dealt with constraints.
def minimize_desired(objective):
p = MixedIntegerLinearProgram(maximization=false)
pvar = p.new_variable(real=True, nonnegative=True)
variables=set(objective.arguments())
translation={v:pvar[v] for v in variables}
objective=objective.subs(translation) # FAILS HERE
p.set_objective(objective)
print p.solve()
def minimize_works(objective):
p = MixedIntegerLinearProgram(maximization=false)
pvar = p.new_variable(real=True, nonnegative=True)
variables=set(str(v) for v in objective.arguments())
translation={v:pvar[v] for v in variables}
objective=sageobj(str(objective), translation)
p.set_objective(objective)
print p.solve()
var('x y')
minimize_works(x+y)
print
minimize_desired(x+y)
millermjSat, 20 Jul 2019 19:24:18 -0500http://ask.sagemath.org/question/47227/Problem of m travelling salesmen (TSP) in Sage. [Linear programming]http://ask.sagemath.org/question/46781/problem-of-m-travelling-salesmen-tsp-in-sage-linear-programming/I have to solve problem of m TSP's by linear programming.
Distances are euclidean, so one of good solutions is when only one salesman visits all the cities.
This is the solution i get when running that program (start city is city number 8, so it is 7th in sage cause we count from 0):
This is link to my program in Cocalc [comments are in Polish]:
- https://share.cocalc.com/share/88eb1fdd-546a-48ea-80b3-c63b047adfa8/kopiasage.ipynb?viewer=share
After running this, i get solution with 1 salesman. However, if in two constraint in for I change <=2 to ==2; that change requires putting 2 salesmen on the battlefield. However, my program still does solution with only one.
Why? In another worksheet I did also with 3, and also I got only 1 salesman when doing ==3 instaed of <=3 in constraints.
I program in Cocalc, not in SageMath installed on PC.
By the way, that forum has extremely annoying captcha - I spent 10 minutes doing it, bcs it always was saying that i picked wrong images....MaciejFicekMon, 03 Jun 2019 15:24:32 -0500http://ask.sagemath.org/question/46781/How to get all the integer solutions to a system of linear equations ?http://ask.sagemath.org/question/45611/how-to-get-all-the-integer-solutions-to-a-system-of-linear-equations/ Hello all,
I am a beginner at Sage and Python.
Is it possible to get all the integer solutions to a system of linear equations ?
I thought i would try to use MLIP for this. The tutorial thematic_tutorials on linear_programming has a call round(p.get_values(x), 2) which shows how to return one solution, but i would like to access all possible solutions.
Thank you in advance!
user3203476Sun, 03 Mar 2019 03:16:57 -0600http://ask.sagemath.org/question/45611/Plot of linear programming restrictions 2d, 3dhttp://ask.sagemath.org/question/45007/plot-of-linear-programming-restrictions-2d-3d/Is there a way automatical plot the restiriction and the solution.
I know how to plot them by hand. Is there an automatical graphical solution included?thethaFri, 11 Jan 2019 04:12:07 -0600http://ask.sagemath.org/question/45007/find one interior point of a polyhedronhttp://ask.sagemath.org/question/10829/find-one-interior-point-of-a-polyhedron/Hi,
I have a bunch of inequations and I would like to know if there is a solution. What is the simplest way to achieve this in Sage ? I tried using MILP with success... but the point returned is not very fancy (often on the boundary). In an ideal world, I would like to optimize some quadratic function in order for the solution to be the nicest possible.
Here is a sample and simple example with only one inequality (other constraints are equalities) where I reproduced the output of MILP:
Constraints:
2.0 <= x_0 + x_7 + x_8 <= 2.0
2.0 <= x_1 + x_2 <= 2.0
2.0 <= x_3 + x_5 + x_9 <= 2.0
2.0 <= x_4 + x_6 <= 2.0
1.0 <= x_0 + x_2 + x_9 <= 1.0
1.0 <= x_5 + x_6 + x_8 <= 1.0
0.0 <= x_2 + x_6 <= 1.0
Variables:
x_0 is a continuous variable (min=0.0, max=2.0)
x_1 is a continuous variable (min=0.0, max=2.0)
x_2 is a continuous variable (min=0.0, max=2.0)
x_3 is a continuous variable (min=0.0, max=2.0)
x_4 is a continuous variable (min=0.0, max=2.0)
x_5 is a continuous variable (min=0.0, max=2.0)
x_6 is a continuous variable (min=0.0, max=2.0)
x_7 is a continuous variable (min=0.0, max=2.0)
x_8 is a continuous variable (min=0.0, max=2.0)
x_9 is a continuous variable (min=0.0, max=2.0)
There are plenty of *nice* solutions, one is
x0 = x2 = x5 = x6 = x8 = 1/3
x1 = x4 = 5/3
x3 = x7 = 4/3
But with the solver I got:
sage: p.solve()
sage: p.get_values(p[1],p[2],p[3],p[4],p[5],p[6],p[7],p[8],p[9])
[1, 2, 0, 2, 2, 0, 0, 0, 1]
ThanksvdelecroixFri, 13 Dec 2013 01:39:30 -0600http://ask.sagemath.org/question/10829/Trouble with mixed integer linear programminghttp://ask.sagemath.org/question/41458/trouble-with-mixed-integer-linear-programming/I'm having trouble with sage's mixed linear programming tool.
I entered the following code trying to maximize a variable with the given constraint that multiplication by a matrix would result in the zero vector.
[picture of inputs is here](https://drive.google.com/file/d/1guE79ATQHZRol0D1PCP9sHpROLi1zTpY/view?usp=sharing)
sage: p = MixedIntegerLinearProgram(maximization = True, solver = "GLPK")
sage: x = p.new_variable(integer = True, nonnegative = True)
sage: p.add_constraint(x*spoof_matrix == 0)
sage: p.set_objective(x[25])
sage: p.solve()
Where spoof_matrix is a 56x34 matrix that has the specific constraints I'm working with.
When I use the p.solve() it gives the error in the picture.
I know that there is at least one non-trivial solution since the test vector seen in the picture solves the constraints.
I don't know why sage isn't solving the optimization problem, and any help would be really great!
Also, if it's possible to not only get the maximum value but also obtain the vector that gives the maximum value, that would be really awesome. Thanks!!
Edit: People have asked for the code for how spoof matrix is created, using these functions the spoof matrix would be given by the following line.
create_spoof_matrix(reduce_n_times(25,generate_possible_factors_list(3),primes_first_n(168),168),168)
def spoof(p,a):
if p*a == 0:
return 1
if p!=1 and a != 1:
value = ((1/p)^(a+1)-1)/(1/p-1)
elif p ==1:
value = (a+1)
elif a ==1:
value = (1+1/p)
return value
def reduce_possible_primes(possible_factors,number_of_primes):
new_prime_list = []
for x in possible_factors:
for p in primes_first_n(number_of_primes):
if x % p == 0:
if p not in new_prime_list:
new_prime_list.append(p)
for x in xrange(0,len(new_prime_list)): #this is just ordering the primes from least to greatest.
for y in xrange(0,len(new_prime_list)):
if new_prime_list[x] < new_prime_list[y]:
cache = new_prime_list[x]
new_prime_list[x] = new_prime_list[y]
new_prime_list[y] = cache
return new_prime_list
def generate_possible_factors_list(size_of_factors):
possible_factors = []
for x in xrange(-1*(10^size_of_factors)+1,10^size_of_factors,2):
if x != -1:
numerator_factor = list(factor(numerator(spoof(x,2))))
if numerator_factor[-1][0] < 10^size_of_factors:
possible_factors.append(x)
return possible_factors
def reduce_possible_factors(possible_factors,possible_primes):
for x in possible_factors:
numerator_factor_bank = list(factor(numerator(spoof(x,2))))
for y in xrange(0,len(numerator_factor_bank)):
if numerator_factor_bank[y][0] not in possible_primes:
if x in possible_factors:
possible_factors.remove(x)
return possible_factors
def reduce_n_times(n,possible_factors, possible_primes, number_of_primes):
x = 0
while x < n:
possible_primes = reduce_possible_primes(possible_factors,number_of_primes)
possible_factors = reduce_possible_factors(possible_factors,possible_primes)
x = x+1
return possible_factors
def create_spoof_matrix(possible_factors,n):
possible_primes = reduce_possible_primes(possible_factors,n)
vector = zero_vector(len(possible_primes))
matrix_list = []
for x in possible_factors:
copy_vector = vector[:]
denominator_list = list(factor(x))
numerator_list = list(factor(numerator(spoof(x,2))))
for y in denominator_list:
copy_vector[possible_primes.index(y[0])] = -2*y[1]
for y in numerator_list:
copy_vector[possible_primes.index(y[0])] = y[1]
matrix_list.append(copy_vector)
return Matrix(matrix_list)JRHalesFri, 09 Mar 2018 18:53:02 -0600http://ask.sagemath.org/question/41458/Linear programing variable dependancyhttp://ask.sagemath.org/question/33428/linear-programing-variable-dependancy/Solving a linear programming problem there input constrains and addition constraints my be generated during solving the problem.
I am only interested in constrains of the form x <= y.
Does sage provide a method to the all the constrains between the variables?
How easy is it to represent the constrain visually?
JohanTue, 17 May 2016 06:46:41 -0500http://ask.sagemath.org/question/33428/Change in linear programming syntaxhttp://ask.sagemath.org/question/25913/change-in-linear-programming-syntax/Until the recent update in SMC to the latest version of Sage, the following would work:
p = MixedIntegerLinearProgram()
x=p.new_variable(nonnegative=True)
y=p.new_variable(nonnegative=True)
z=p.new_variable(nonnegative=True)
p.set_objective(x + y+ 3*z)
This now gives an error saying that * and + are not defined for these objects.
The following does work, however:
p = MixedIntegerLinearProgram()
x=p.new_variable(nonnegative=True)
y=p.new_variable(nonnegative=True)
z=p.new_variable(nonnegative=True)
p.set_objective(x[0] + y[0]+ 3*z[0])
So, are all new variables in an MILP assumed to be arrays? Is there are way to work with variables as in my first example without using subscripts? (This is mainly for teaching purposes.)
calc314Tue, 24 Feb 2015 07:35:43 -0600http://ask.sagemath.org/question/25913/How to stop a MILP before it reaches the optimal solution (using different backends)?http://ask.sagemath.org/question/25909/how-to-stop-a-milp-before-it-reaches-the-optimal-solution-using-different-backends/Sometimes you don't need an optimal solution. A feasible solution is a must, but a decent value of the objective function will do. At least that's better than waiting forever...
Some backends (most?, all?) for the MixedIntegerLinearProgram support different stop criteria. But it took me quite some time to find them. How to tell MixedIntegerLinearProgram not to continue until the optimal solution is found?
PD: I found the answer (at least part of it) before I submitted this question, but I think it's good to ask the question for reference:pangTue, 24 Feb 2015 03:19:05 -0600http://ask.sagemath.org/question/25909/Sage+Gurobi: Can I control how many processors vertex_coloring uses?http://ask.sagemath.org/question/25819/sagegurobi-can-i-control-how-many-processors-vertex_coloring-uses/I am using Sage to color some graphs, using a 32-processor Linux server. I am using the vertex_coloring command, with Gurobi as the LP solver.
I've noticed that for graphs that take more than a few minutes, the program seems to eventually settle on using 16 processors. It would be nice if I could tell Sage (or Gurobi?) to allow more or fewer processors. Is this possible?
MattKahleThu, 12 Feb 2015 18:32:19 -0600http://ask.sagemath.org/question/25819/Is there a bug with using chromatic_number together with Gurobi?http://ask.sagemath.org/question/25564/is-there-a-bug-with-using-chromatic_number-together-with-gurobi/I have installed the LP solver Gurobi, and it seems to work successfully work with the vertex_coloring() command. But I wanted to compare runtimes with chromatic_number, and Sage seems to hang whenever I try this.
I construct a graph G, and then when I run the command G.chromatic_number(algorithm="MILP"), Sage hangs. I can tell something has gone wrong because it doesn't come back even when I give it a very small simple graph G, and because Linux tells me that I know have a zombie process.
Any suggestions would be much appreciated.
MattKahleMon, 19 Jan 2015 15:19:01 -0600http://ask.sagemath.org/question/25564/setting default LP solverhttp://ask.sagemath.org/question/25455/setting-default-lp-solver/I installed Gurobi, and have gotten Sage to recognize it. So when I use a command such as vertex_coloring(G,solver="GUROBI") everything works fine.
But what if I want to use instead a command such as G.chromatic_number(algorithm="MILP"). How do I make sure that the LP solver that Sage is using is Gurobi, rather than GLPK? Is there one place I can tell Sage that it should always default to Gurobi as its LP solver, or is it possible that Sage is smart enough that once Gurobi is installed it does that anyway?
(Also, peripherally: does anyone have any idea whether chromatic_number or vertex_coloring is more efficient for large graphs?)
MattKahleFri, 09 Jan 2015 13:34:34 -0600http://ask.sagemath.org/question/25455/How to solve linear programming in matrix form?http://ask.sagemath.org/question/24138/how-to-solve-linear-programming-in-matrix-form/ Some times I have to solve large scale linear programming where the the constraints are given in matrix.
However, all tutorials provided only demonstrate very small scale cases. What if I have a linear programming given in a 1000*400 matrix. How to solve such a linear programming in Sage? Do I need to use another package to solve such linear programming problems?HanMon, 15 Sep 2014 08:57:38 -0500http://ask.sagemath.org/question/24138/Use of constraint_generation in MixedIntegerLinearProgramhttp://ask.sagemath.org/question/10915/use-of-constraint_generation-in-mixedintegerlinearprogram/I would like to solve an LP problem using row generation (aka constraint generation), where I wish to be able to choose how the constraints are generated (this will be done using SAT, or WPMaxSAT through a binary MIP).
Now, in MixedIntegerLinearProgram, there is a boolean option `constraint_generation`. I do not find an explanation of its use and therefore whether it can be used for my stated purpose. So, can I, and if so, how?
Information found, but which did not make th option clear to me:
From the [documentation](http://www.sagemath.org/doc/reference/numerical/sage/numerical/mip.html):
> constraint_generation whether to require the returned solver to support constraint generation (excludes Coin). False by default.
From the [source code documentation](http://https://github.com/sagemath/sage/blob/master/src/sage/numerical/backends/generic_backend.pyx#L983):
> - ``constraint_generation`` (boolean) -- whether the solver returned is to be used for constraint/variable generation. As the interface with Coin does not support constraint/variable generation, setting ``constraint_generation`` to ``False`` ensures that the backend to Coin is not returned when ``solver = None``. This is set to ``False`` by default.
(N.B.: Shouldn't that be: backend to Coin is not returned -> Coin backend may be returned?)Erik QuaeghebeurWed, 15 Jan 2014 02:51:10 -0600http://ask.sagemath.org/question/10915/Use os SOS2 in Linear Optimizationhttp://ask.sagemath.org/question/10679/use-os-sos2-in-linear-optimization/I have a linear optimization to minimize value like
MIN = sum(x_i*j_i)
Constrains:
0 < x_i < C
0 < j_i < J
x_i + y_i <= x_(i-1) + f(x_i)
Where this f(x_i) is a SOS2 function:
Sum(lambda_i) = 1
Sum(lambda_i * X_i) = x_i # Here X_i is a constant.
Sum(lambda_i * K_i) = result # Here K_i is a constant.
this result will be returned.
When I make individual MixedIntegerLinearProgram(maximization=False, solver = "GLPK") one for f(x), I am able to slove. When introducing the function as another variable into another MixedIntegerLinearProgram(maximization=False, solver = "GLPK") I am unable to get the results.
Need help in actually formulating the sage equations.
subbuThu, 31 Oct 2013 18:20:01 -0500http://ask.sagemath.org/question/10679/Output results of sage MixedIntegerLinearProgram solution are not as expectedhttp://ask.sagemath.org/question/10827/output-results-of-sage-mixedintegerlinearprogram-solution-are-not-as-expected/For the problem below
------------------------
<pre><code>#!/usr/bin/sage -python
from sage.all import *
import sys
problem = MixedIntegerLinearProgram(maximization=False, solver = "GLPK")
y = problem.new_variable(real=True, name='y')
constraints_1 = [(0.0, 6769.0),
(8260.0, 6812.0),
(12390.0, 7105.0),
(16520.0, 7448.0),
(20650.0, 7924.0),
(24780.0, 8289.0),
(28910.0, 8630.0),
(33040.0, 9000.0)]
sos_var_1 = problem.new_variable(name='sos2_var')
eq1_1 = 0.0
eq1_2 = 0.0
eq1_3 = 0.0
for i in range(len(constraints_1)):
eq1_1 += sos_var_1[i]*constraints_1[i][0]
eq1_2 += sos_var_1[i]*constraints_1[i][1]
eq1_3 += sos_var_1[i]
problem.add_constraint(eq1_1 == 23450)
problem.add_constraint(eq1_2 == y[0])
problem.add_constraint(eq1_3 == 1)
problem.set_objective(y[0])
print problem.solve()
</code></pre>
--------------------------------
I am expecting the result to be 8136 but I am getting <pre><code>8099.05084746</code></pre>
Can anyone help or explain why this is happening?subbuThu, 12 Dec 2013 09:01:29 -0600http://ask.sagemath.org/question/10827/Linear programming with algebraic numbershttp://ask.sagemath.org/question/10357/linear-programming-with-algebraic-numbers/Is it possible to use one of the built in routines for linear programming with algebraic numbers, instead of floating point numbers.
I have to solve a problem on algebraic operators exactly, not numerically.Klaus ScheicherTue, 16 Jul 2013 21:24:26 -0500http://ask.sagemath.org/question/10357/How to get slack values when using GLPK backend?http://ask.sagemath.org/question/10352/how-to-get-slack-values-when-using-glpk-backend/Hello,
When using sagemath to compute a linear programming problem(using GLPK backend), is there a way to get the slack values other than the full p.print_ranges()?
that is just send the slacks(surplus) to a variable or vector?
Thanks.ShimiMon, 15 Jul 2013 02:17:24 -0500http://ask.sagemath.org/question/10352/binary linear programminghttp://ask.sagemath.org/question/9499/binary-linear-programming/to whom it may concern
greeting
I have written a binary linear programing. It seems ok.
But the result is
MIPSolverException: 'GLPK : Solution is undefined'
I will appreciate if you can help me and describe the reason
Regards
Aissan Aissan DalvandiSat, 03 Nov 2012 06:39:15 -0500http://ask.sagemath.org/question/9499/p.show() at MixedIntegerLinearProgram resultshttp://ask.sagemath.org/question/8984/pshow-at-mixedintegerlinearprogram-results/I would appreciate it if someone could explain me how the p.show() method works (p=MixedIntegerLinearProgram)...
More precisely :
lets say we have the following Linear Program:
p=MixedIntegerLinearProgram()
w=p.new_variable()
p.add_constraint(-w[0]+w[2]+2*w[3]==4)
p.add_constraint(w[0]+w[1]+w[3]==3)
p.set_objective(w[0]- w[1]) #<---- Look here
the result from p.show() is
Maximization:
x_0 -x_3 #<----and here
Constraints:
4.0 <= -x_0 +x_1 +2.0 x_2 <= 4.0
3.0 <= x_0 +x_2 +x_3 <= 3.0
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
x_2 is a continuous variable (min=0.0, max=+oo)
x_3 is a continuous variable (min=0.0, max=+oo)
why SAGE shows a different objective function?
koukourikosSat, 19 May 2012 10:00:54 -0500http://ask.sagemath.org/question/8984/linear programming in cythonhttp://ask.sagemath.org/question/8952/linear-programming-in-cython/hi,
i am trying to speed up a sage code in cython and i am having difficulties with calling the linear programming routine.
my algorithm requires me to solve a large number of linear programs. currently, i am doing this in sage by calling MixedLinearProgram inside a loop and updating variables depending on the solution.
is there a way to call that program inside a cython function? i would need a cython program that accepts arrays as inputs, solves a linear program and outputs an array.
many thanks for your help
markusmarkusFri, 04 May 2012 15:27:38 -0500http://ask.sagemath.org/question/8952/Memory blowup with MILPhttp://ask.sagemath.org/question/8729/memory-blowup-with-milp/Hello, I have been running some code on our Sage server and it ends up using a huge amount of memory, up to around 50 GB, and then eventually stops running. No error message is generated. It's just that the green bar is gone and it isn't doing anything. This code should generate the problem. When I ran this, it ran up to around 300,000 graphs and then stopped. It should run through all 12.7 million without stopping.
count = 0
for g in graphs.nauty_geng("10"):
count = count + 1
if count % 50000 == 0:
print count
vcc = int(round(g.complement().chromatic_number(algorithm = "MILP")))
if vcc == 9:
print g.graph6_string()
Now, I talked to Jason Grout later and he mentioned that if I changed it to algorithm = "CP", not only does the memory problem not occur, it is also faster on smaller graphs. But, there is still the problem with the MILP algorithm that should be addressed at some point, I assume.
Thanks
**UPDATE:** I tried the gc.collect() and want to say it doesn't do anything.
g = graphs.PetersenGraph()
for count in [1..100000]:
if count % 5000 == 0:
print count
print get_memory_usage()
gc.collect()
print get_memory_usage()
test = g.independent_set()
the get_memory_usage() keeps getting higher and higher and higher as I do this. The way I got it to reset was to save and quit the worksheet.
Not a huge deal because we have a better fix coming, it appears. But, just wanted to point out that gc.collect() doesn't seem to do anything as far as I can tell.
**UPDATE 2:** The patch didn't work. There is still a memory leak. Here is the exact code I am running this time, after the patch was installed to our Sage server.
count = 0
for g in graphs.nauty_geng("10"):
if count % 50000 == 0:
print count
print get_memory_usage()
count = count + 1
vcc = int(round(g.chromatic_number("MILP")))
The memory usage at 0 was 808. At 50000, it was 3145. At 100000, it was 8106. At 200000, we're up to 14369.G-SageTue, 21 Feb 2012 06:56:23 -0600http://ask.sagemath.org/question/8729/How to report a mistake in the documentation?http://ask.sagemath.org/question/8277/how-to-report-a-mistake-in-the-documentation/I have detected a mistake in the Thematic Tutorial "Linear Programming (Mixed Integer)", in the instructions to install the GUROBI solver. How can I report it?igngvsSat, 04 Feb 2012 05:35:35 -0600http://ask.sagemath.org/question/8277/