ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 03 Jun 2021 02:50:34 +0200min-max-ing a function with sagehttps://ask.sagemath.org/question/57427/min-max-ing-a-function-with-sage/Suppose S is a family of k matrices. Then, given formal variables x[0], ... , x[k], consider the expression min(x[0] * S[0] + ... + x[k-1]*S[k-1]). I want to maximize the value of this expression with respect to the constraints x[0],...x[k] >= 0 and x[0] + ... + x[k] = 1.
This is the corresponding mathematica code:
\[Beta][T_] :=
With[{vars = Array[x, Length[T]]},
Maximize[{Min[Total[MapThread[Times, {vars, T}]]], (And @@ Thread[vars >=0])&& Total[vars] == 1},vars]
]
How can I define this in sage?
I have thought of using `sage.numerical.optimize.minimize_constrained` but I do not particularly like it because it (unlike mathematica) seems to give inexact values.chlamydomonasThu, 03 Jun 2021 02:50:34 +0200https://ask.sagemath.org/question/57427/solving a matrix equation in the integers.https://ask.sagemath.org/question/53262/solving-a-matrix-equation-in-the-integers/ I'm trying to use sage to solve an expression of the form $xS = y$ for a fixed integer matrix $S$ and a fixed integer vector $y$. I need my solution vector $x$ to also have integer coefficients.
How I'm currently doing this is by using the mixed integer linear programming tool and my code looks something like this.
p = MixedIntegerLinearProgram(maximization = True, solver = "GLPK")
x = p.new_variable(integer = True, nonnegative = True)
p.add_constraint( x*S == y) #here the vector can be anything
p.add_constraint( x[25] <= 2020 )
p.set_objective( x[25] )
p.solve()
p.get_values(x)
The issue I have here is that the objective and the constraint are arbitrary and were just picked so that the space that the MixedIntegerLinearProgram function is trying to optimize over has a "feasable solution" (sage's words not mine). Is there a better way to find a solution to $xS = y$ in the integers (i.e a different function or package supported by sage) and if not, is there a way to have my constarint be to make the norm of the vector as small as possible (so that I'm not just artificially picking an entry to optimize my search over)?
JRHalesWed, 02 Sep 2020 18:10:13 +0200https://ask.sagemath.org/question/53262/Is there a macro solving transportation problems stage by stage?https://ask.sagemath.org/question/48897/is-there-a-macro-solving-transportation-problems-stage-by-stage/ I would like something using the special structure of the problem, for teaching purposes, like the wonderful
InteractiveLPProblem for linear programming. ThanksflorinTue, 26 Nov 2019 18:46:35 +0100https://ask.sagemath.org/question/48897/Double indexed variables in linear programminghttps://ask.sagemath.org/question/48702/double-indexed-variables-in-linear-programming/The following linear programming code works perfectly.
nlg=4 #nombre de contraintes
mlg=6 #nombre de variables
Alg= matrix(nlg,mlg,[0,0,0,1,1,1,
1,0,0,1,0,0,
0,1,0,0,1,0,
1,1,3,0,0,0
]) # les coefficients
blgmin = [1,0,0,1] # les bornes inférieures pour les contraintes
blgmax = [1,0,0,3] # les bornes supérieures pour les contraintes (oo = infini)
show(LatexExpr('A = '),Alg)
show(LatexExpr('bmin = '),blgmin)
show(LatexExpr('bmax = '),blgmax)
lg = MixedIntegerLinearProgram(maximization=False, solver = "GLPK") # on crèe le programme
x = lg.new_variable(integer=True, indices=[0..mlg-1]) # les nouvelles variables sont x[0] ... x[5]
Blg = Alg * x # la fonction linéaire pour les contraintes
lg.set_objective(x[0])# fixe l’objectif
# On construit les contraintes avec leurs bornes
for i in range(nlg) :
lg.add_constraint(Blg[i], min=blgmin[i], max=blgmax[i])
for i in range(mlg-1) :
lg.set_binary(x[i])
lg.show()
lg.solve()
xx=lg.get_values(x)
show(xx)
But now, for an other problem, I would like to define
1) variables with other names
2) double indexed variables
Is this possible ?
CyrilleTue, 12 Nov 2019 06:41:44 +0100https://ask.sagemath.org/question/48702/maximizing sum over feasible set of vectorshttps://ask.sagemath.org/question/48630/maximizing-sum-over-feasible-set-of-vectors/Let $[5]$ be the set of the first 5 positive integers. We let $\underline{\alpha} =(\alpha_A)_{A\neq \emptyset, A\subseteq [5]}$ consist of a vector with $31$ real entries, where each $\alpha_A$ is associated with a subset $A \subseteq [5]$.
Define $\displaystyle OBJ(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A \log(|A|)$, $\quad \displaystyle v(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A$, $\quad$ and $\quad \displaystyle E(\underline{\alpha})=\sum_{ {A,B}: A\cap B\neq \emptyset} \alpha_A \alpha_B$,
where the sum for $E(\underline{\alpha})$ is taken over all unordered pairs of disjoint nonempty sets $A$ and $B$, where $A, B \subseteq [5]$.
Also define $FEAS(1/4)$ to be the set of all such vectors $\underline{\alpha}$ with nonnegative real entries such that $v(\underline{\alpha})=1$ and $E(\underline{\alpha})\geq 1/4$.
I want to learn how to program the following optimization problem:
$$\displaystyle OPT(1/4):=\max_{\underline{\alpha} \in FEAS(1/4)} OBJ(\underline{\alpha})$$
I was told that I can do this in SageMath. I have some basic knowledge of how to use Sage. How could I create the set $FEAS(1/4)$? I think that from there I may be able to figure out how to maximize $OBJ(\underline{\alpha})$ over this set.merluzaTue, 05 Nov 2019 22:28:50 +0100https://ask.sagemath.org/question/48630/Strange result with GLPKhttps://ask.sagemath.org/question/48360/strange-result-with-glpk/This program
%display latex
m=3
n=2
A=matrix(m,n,(0,1,1,0,6,18))
bmin=[12,0,70]
bmax=[oo,10,70]
c=matrix(1,n,(4.1,8))
show(A,bmin,bmax,c)
p = MixedIntegerLinearProgram(maximization=False, solver = "GLPK")
x = p.new_variable(integer=False, indices=[0..n-1]) # les nouvelles variables seront x[1]... x[7]}
B = A * x # m
for i in range(m):
p.add_constraint(B[i], min=bmin[i], max=bmax[i])
for i in range(n):
p.set_min(x[i],0)
p.set_objective(4.1*x[0]+8*x[1])
p.show()
p.set_min(x[i],0)
p.set_objective(4.1*x[0]+8*x[1]
p.show()
p.solve()
has obviously no solution as show by the result of
z=p.polyhedron()
zz=z.vertices()
zz
(There are no vertices)
but
p.solve()
gives 96 and
valeurs=p.get_values(x)
valeurs
gives
$\{0:0.0,1:12.0\}$
but $18 *12 =216 \geq 70$ wich shows the assertion
CyrilleWed, 16 Oct 2019 11:11:25 +0200https://ask.sagemath.org/question/48360/Linear Programming: float solving and exact verificationhttps://ask.sagemath.org/question/48034/linear-programming-float-solving-and-exact-verification/Hi there,
the glpsol tool (GLPK) provides an option "--xcheck": the solver compute the optimal solution uses floating points, and then checks the correctness using exact arithmetics (i guess implicitly they re-check the basis variables, so this only requires one matrix inversation on exact arithmetics)
1. the MILP interface of sage provides the possibility to set, however, it appears that there is no option to activate "xcheck"?
[not allowed to post links but here are the references for the sage documentation] doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html#sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter
doc.sagemath.org/html/en/reference/numerical/sage/numerical/backends/glpk_backend.html#sage.numerical.backends.glpk_backend.GLPKBackend.solver_parameter
2. I know that it is easy to extract the basis variables and to recheck the correctness of a floating-point-solution just within sage, however, I really think **this should be added as a basic functionality** for the SAGE MILP interface to ANY solver, not only GLPK (so this verification-code should also verify solutions of cplex,gurobi,etc.) .
So, does anyone have already an implementation for such a verification?
Best,
ManfreddeadalpsSun, 22 Sep 2019 23:33:46 +0200https://ask.sagemath.org/question/48034/