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, 12 Aug 2021 04:26:37 +0200Sage9.3 getting MILP model status after solve()https://ask.sagemath.org/question/58417/sage93-getting-milp-model-status-after-solve/I'm using Sage9.3 MixedIntegerLinearProgram. After attempting to solve a milp problem M using M.solve(), when the program stops it could be<br>
- M is solved with solution<br>
- M is infeasible<br>
- timeout (which I have imposed)<br>
- terminated by some external factor<br>
Is there a way (or function) to determine the status of M?
I'm using both GLPK and Gurobi, so would appreciate solutions for both solvers.
Thanks.SimThu, 12 Aug 2021 04:18:10 +0200https://ask.sagemath.org/question/58417/Sage9.3 get best_known_objective_bound() for Gurobi solverhttps://ask.sagemath.org/question/58418/sage93-get-best_known_objective_bound-for-gurobi-solver/Hi,
I'm using Gurobi as the solver, after a timeout, I want to see what is the best bound found so far
p = MixedIntegerLinearProgram(solver="Gurobi")<br>
\#\#add milp model to p\#\#<br>
p.solve()<br>
upper_bound = p.get_objective_value()<br>
lower_bound = p.best_known_objective_bound()
But I will get an error for best_known_objective_bound(), it works for GLPK so I'm wondering if there is a similar function for Gurobi solver as well.SimThu, 12 Aug 2021 04:26:37 +0200https://ask.sagemath.org/question/58418/solver parameter not available in Mixed Integer Linear Programminghttps://ask.sagemath.org/question/55959/solver-parameter-not-available-in-mixed-integer-linear-programming/I'm getting the following error, while trying to set up [IntegralityFocus](https://www.gurobi.com/documentation/9.1/refman/integralityfocus.html) for Gurobi backend in Sage 9.2:
sage: from sage_numerical_backends_gurobi.gurobi_backend import GurobiBackend as mysolver
sage: milp = MixedIntegerLinearProgram(solver=mysolver)
sage: milp.solver_parameter("IntegralityFocus", 1)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
sage_numerical_backends_gurobi/gurobi_backend.pyx in sage_numerical_backends_gurobi.gurobi_backend.GurobiBackend.solver_parameter()
KeyError: 'IntegralityFocus'
During handling of the above exception, another exception occurred:
ValueError Traceback (most recent call last)
<ipython-input-3-65373ae60dc1> in <module>
----> 1 milp.solver_parameter("IntegralityFocus", Integer(1))
/usr/local/SageMath.92/local/lib/python3.8/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter (build/cythonized/sage/numerical/mip.c:16597)()
2470 return self._backend.solver_parameter(name)
2471 else:
-> 2472 self._backend.solver_parameter(name, value)
2473
2474 cpdef sum(self, L):
sage_numerical_backends_gurobi/gurobi_backend.pyx in sage_numerical_backends_gurobi.gurobi_backend.GurobiBackend.solver_parameter()
ValueError: This parameter is not available. Enabling it may not be so hard, though.
Ok, it says *"Enabling it may not be so hard, though."* but **HOW?**Max AlekseyevSun, 28 Feb 2021 23:20:12 +0100https://ask.sagemath.org/question/55959/values of variables from points in the polyhedron defined by a linear programhttps://ask.sagemath.org/question/55520/values-of-variables-from-points-in-the-polyhedron-defined-by-a-linear-program/SageMath provides a [function](https://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html#sage.numerical.mip.MixedIntegerLinearProgram.polyhedron) for constructing the polyhedron defined by a linear program. Given a point in such a polyhedron, how can I tell which coordinate of the point corresponds to which variable of the linear program?
**ADDED:** The documentation suggests that "the polyhedron is built from the variables stored by the LP solver" and that "they usually match the ones created explicitly when defining the LP", except possibly for Gurobi solver. So, the question seems to reduce to finding the order number of each variable in LP (or an accurate bookkeeping of their creations). Things are even more fuzzy for Gurobi, which one of the best solvers out there.Max AlekseyevSun, 31 Jan 2021 19:51:48 +0100https://ask.sagemath.org/question/55520/What happened to the dim parameter of new_variable?https://ask.sagemath.org/question/49227/what-happened-to-the-dim-parameter-of-new_variable/ Hello, Sage community!
I remember I could do this in order to have a bi-indexed variable for MILPs:
LP = MixedIntegerLinearProgram(maximization=True)
x = LP.new_variable(nonnegative=True, dim=2)
So, the syntax `x[1][2]` is valid. This behavior is documented in some books and manuals for SageMath (perhaps, a little dated now).
However, I just tried to do this in one of my programs, and Sage responded:
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-15-350071b4e772> in <module>()
----> 1 x = LP.new_variable(nonnegative=True, dim=Integer(2))
/Scientific/SageMath/local/lib/python3.7/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.new_variable (build/cythonized/sage/numerical/mip.c:6019)()
701 self._backend.problem_name(name)
702
--> 703 def new_variable(self, real=False, binary=False, integer=False, nonnegative=False, name="",
704 indices=None):
705 r"""
TypeError: new_variable() got an unexpected keyword argument 'dim'
Actually, `LP.new_variable??` shows me the signature of the `new_variable` function, but the `dim` argument is missing.
Did something change? How can I get the same behavior now?
**SageMath version: 9.0-beta8**
Thanks in advance!dsejasFri, 27 Dec 2019 18:02:45 +0100https://ask.sagemath.org/question/49227/Possible bug: GLPKError/assertion failedhttps://ask.sagemath.org/question/48375/possible-bug-glpkerrorassertion-failed/ Hello, Sage Community!
Recently, while trying to help one of the users of this forum, I wrote [this code](https://sagecell.sagemath.org/?z=eJyFkVFrwjAQx98L_Q6HvtRRiw5BGfRBHzZkOnzYWxFJ27TeaJOSpLYM9t130VZFGGsCzT_t_e5_d0sIoWRGYest_JkfTX27xtOZP6H3sz9ekDjfTbo1vhe3053ej2AI5sghkTzLMEEujHaduERB2aIrpgvad38XsuEKYlmLVEMmVYcQ2iiGHYG1PUHKh91j6qr6B1MRY4stT9fC8JyrDQrO1E7JXLHSoxxY4jczKEX4ygrNfdCyOBE0hMHbZvc-sPU1BFWcGX7mb9ebnetYc1UgeHM4MYUsLriHlxThp6qJgyLFhOswmgTB_NomCoA-ABosCog5tBE1JggCOsx_XGdF6CU8Qds36-wZslok1ugflQ7hQzbWalxjkT5-h1qjyM-3XbsK1DbMspDMgmIi595i9OI6QE8VsDQ93AjeKsK9DzTX0A73Ilgb2jmRGFGrA32UjXepFDXQ_qq1ASOtkQxVad2lmAIaUJgfzS_OfM4l&lang=sage&interacts=eJyLjgUAARUAuQ==). As you can see, the MILP is defined as expected.
That was a few weeks ago. Just now, I have noticed that adding `p.solve()` produces an error/exception:
> GLPKError: Assertion failed: j->lb < j->ub
> Error detected in file glpnpp03.c at line 2134
According to this, the problem seems to be in a C (maybe Cython) subroutine, which I am not able to modify. The strange thing is that defining this same MILP, manually, using the data showed there, does not produce any error! That what makes me think this is a bug.
Here is the complete traceback:
---------------------------------------------------------------------------
GLPKError Traceback (most recent call last)
<ipython-input-1-fbad4ef266dd> in <module>()
9 p.add_constraint(B[i], min=bmin[i], max=bmax[i])
10 p.show() # this is just to confirm we did it right
---> 11 p.solve()
/home/sc_serv/sage/local/lib/python2.7/site-packages/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:15815)()
2259 """
2260 if log is not None: self._backend.set_verbosity(log)
-> 2261 self._backend.solve()
2262 return self._backend.get_objective_value()
2263
/home/sc_serv/sage/local/lib/python2.7/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:9430)()
1060 if ((self.simplex_or_intopt == glp_intopt_only)
1061 or (self.simplex_or_intopt == glp_simplex_then_intopt) and (solution_status != GLP_UNDEF) and (solution_status != GLP_NOFEAS)):
-> 1062 sig_on()
1063 solve_status = glp_intopt(self.lp, self.iocp)
1064 solution_status = glp_mip_status(self.lp)
GLPKError: Assertion failed: j->lb < j->ub
Error detected in file glpnpp03.c at line 2134
Thanks in advance for your answers!dsejasWed, 16 Oct 2019 21:06:27 +0200https://ask.sagemath.org/question/48375/Solve MILP by reading LP fileshttps://ask.sagemath.org/question/44817/solve-milp-by-reading-lp-files/Sage has a wide range of solvers available to [solve MILP](http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html) problems. However, all these functionalities require that the problem is to be implemented following Sage's API.
In contrast, Gurobi allows to solve MILP problems, directly reading from an [LP file](http://www.gurobi.com/documentation/8.1/refman/lp_format.html). This comes in handy, as there's no need to follow Sage API. If the LP file is too large to handle, then the user can simply write another program that will create this file. Apart from being simple and scalable, LP formats can be used for porting to other (unsupported) library.
It seems that, Sage does not yet support directly reading LP files. It will be helpful if someone can comment specifically if such functionality is available or will be implemented in near future/a ticket can be initiated.ppSun, 30 Dec 2018 20:23:59 +0100https://ask.sagemath.org/question/44817/Basic MILP problemhttps://ask.sagemath.org/question/44204/basic-milp-problem/Hi, I am wondering how I would solve this problem in GAMS.
https: //imgur.com/a/yUcp6Gj (remove space after https:)
Thank you in advance.Joe_Green123Tue, 06 Nov 2018 17:14:06 +0100https://ask.sagemath.org/question/44204/Execution time vs. Computation time in MILPhttps://ask.sagemath.org/question/30495/execution-time-vs-computation-time-in-milp/ Hi,
I am using GLPK in Sage 6.9 to solve MILP problem. I am also using the `Solver_parameter('timelimit')` to terminate the problem after the specficied time. According to [SageMath documentation](http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html), `"timelimit" defines the maximum time spent on a computation. Measured in seconds.` However, I am a bit confused with this definition. This is because:
I am solving `the same problem` with `the same timelimit value` for `different input values (generated randomly using uniform distribution)` while I was printing `execution time` of each. I have noticed `different execution times` when I am giving `different inputs` (ranging from 1min, 5mins, to even 10mins).
Can some one please tell me how the `computation time` is calculated for timelimit? Why they are different even though I used the same problem with the same timelimit? Is it something related to the size of the input, as its only difference between them? Is there any relation between `computation` and `execution` times?
Cheers,
Aissan
Aissan DalvandiFri, 06 Nov 2015 03:24:44 +0100https://ask.sagemath.org/question/30495/solver_parameter('timelimit') doesnt workhttps://ask.sagemath.org/question/30420/solver_parametertimelimit-doesnt-work/Hi,
I have an MILP problem and trying to solve it with Sage, GLPK solver. As I want to terminate the problem before getting the optimum answer, I am using the `p.solver_parameter("timelimit", 60)`. I have also used
try:
p.solve()
except MIPSolverException:
b = p.get_backend()
print('best known opjective bound', b.best_known_objective_bound())
However, the solver doesn't stop!!! It keeps runing. I guess the `time limit` part doesn't work.
Its interesting that the `p.solver_parameter("time limit")` its affected, as I am printing its value before passing the `p.solve()`. I have also tried `p.solver_parameter( backend.glp_simplex_or_intopt, backend.glp_intopt_only)` and printed the `p.solver_parameter("time limit_intopt")`. It's printing `60000` which is right.
I have no idea why it keeps running.
Could anyone help me with this issue?
Thanks in advance,
Cheers,
AissanAissan DalvandiTue, 03 Nov 2015 07:47:45 +0100https://ask.sagemath.org/question/30420/best_known_objective_bound()https://ask.sagemath.org/question/30366/best_known_objective_bound/ Hi,
I am using sage Version 6.5, Release Date: 2015-02-17. I have MILP problem and trying to solve it. However, I defined time limit and used try and except to get the best_known_objective_bound(). Unfortunately, I am getting AttributeError: 'sage.numerical.backends.glpk_backend.GLPKBackend' object has no attribute 'best_known_objective_bound'
I even tried the following simple example (posted here
http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/backends/glpk_backend.html#sage.numerical.backends.glpk_backend.GLPKBackend.best_known_objective_bound). However, I am facing the same issue for the example as well.
sage: g = graphs.CubeGraph(9)
sage: p = MixedIntegerLinearProgram(solver="GLPK")
sage: p.solver_parameter("mip_gap_tolerance",100)
sage: b = p.new_variable(binary=True)
sage: p.set_objective(p.sum(b[v] for v in g))
sage: for v in g:
....: p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1)
sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution
sage: p.solve() # rel tol 100
1.0
sage: backend = p.get_backend()
sage: backend.best_known_objective_bound() # random
AttributeError: 'sage.numerical.backends.glpk_backend.GLPKBackend' object has no attribute 'best_known_objective_bound'
What I want is to get the best known optimum answer by time limit.
Anyone knows how should i get it?
Thanks a lot!
Cheers,
Aissan Aissan DalvandiSat, 31 Oct 2015 05:55:14 +0100https://ask.sagemath.org/question/30366/Change in linear programming syntaxhttps://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 14:35:43 +0100https://ask.sagemath.org/question/25913/How to stop a MILP before it reaches the optimal solution (using different backends)?https://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 10:19:05 +0100https://ask.sagemath.org/question/25909/Lagrange multipliershttps://ask.sagemath.org/question/10798/lagrange-multipliers/When using Mixed Integer Linear Programming to find the minimum of a linear function $f(x_1,...,x_n)$ under a set of constraints $c_i(x_1,...,x_n)$ (equality or inequality constraints), I would like to have not only the solution and value but also the Lagrange multipliers for the constraints, namely values $a_i$ such that, at the critical point:
$$\text{grad} f = \sum_i a_i \cdot \text{grad} c_i$$
I imagine that the algorithm knows about them, but I can't find the relevant method to extract it. Pascal RomonTue, 03 Dec 2013 16:52:55 +0100https://ask.sagemath.org/question/10798/Why do I get the "unable to find a common ring for all elements" error message?https://ask.sagemath.org/question/10746/why-do-i-get-the-unable-to-find-a-common-ring-for-all-elements-error-message/I was wondering if you can take a look at this cell:
http://sagecell.sagemath.org/?q=ypqhgw
and let me know why I get the error message.
ThanksBehzadSun, 17 Nov 2013 20:46:09 +0100https://ask.sagemath.org/question/10746/Un bounded Answer MILPhttps://ask.sagemath.org/question/10217/un-bounded-answer-milp/Hello
I have an MILP problem ....
I set the max of the all variables but some times the sage give me un bounded answer .....
Do you have any suggestion ...
I even considered a constraint which is ( the objective function < T ) and defined T as a Integer variable and minimized the T ....
but still it happened some times ......
Best
Aissan Aissan_DalvandiTue, 11 Jun 2013 10:08:39 +0200https://ask.sagemath.org/question/10217/wrong Answer in MILP :sagehttps://ask.sagemath.org/question/10203/wrong-answer-in-milp-sage/hello everyone ....
I have MILP optimization problem. when I solve the problem and use the get_values function:
Although I sets the variables BINARY but it give me real values like(+0.0) or (-0.0)....
it caused I get the value wrong because when i check the value ==0 or ==1 in this case i receive the wrong answer.....
any suggestion.....???
Thanks
Aissan Aissan_DalvandiThu, 06 Jun 2013 22:25:32 +0200https://ask.sagemath.org/question/10203/