Hot answers tagged

11

I like Stuart Mitchell's (maintainer of Pulp) tips, especially tip number 2 : use a profiler to track your bottlenecks. Quoting him: I can't tell you the number of times I have assumed the slow code was for one reason and then found it was another. I agree with him and use line_profiler to optimize the code (for Python). I have been able to drastically ...


11

Excel remains extensively used in industry for non-OR applications. That means that if you are doing an OR application that does not require access to a database, there's a good chance the data for the application will come to you in either an XLSX or CSV file. On the flip side, when it comes time to convey the solution provided by your application, it is ...


9

MATLAB is a language built on top of a library. Python (with NumPy & numba) is a language with a library built under it. Neither is ideal. Like all languages, both have a few quirks, due to their history. My suggestion: Door Number 3, Julia. In either case (MATLAB, Python, Julia), you should ask yourself: Is your immediate goal to master the math, or to ...


9

You have fallen victim to the renewal paradox, a.k.a. inspection paradox, a.k.a. length-biased sampling. $F_{\Delta}$ is the distribution of service time for the kth customer, but it is NOT the distribution of service time for the customer being served at a preselected time $T$. The very manner of selecting the customer based on observing at a preselected ...


9

There are many ways to do this. Here is a popular one: define a binary variable $x_i$ per interval $[b_i,b_{i+1}]$ and use the following constraints: \begin{align*} 1&=x_0+x_1+\cdots+x_n \tag{1}\\ 0x_0 + (b_0+\epsilon)x_1 + \cdots+ (b_{n-1}+\epsilon)x_n \le Y_t &\le b_0x_0 + b_1x_1 + \cdots+ b_nx_n \tag{2}\\ r_t &\ge f_i - M_i(1-x_i) \tag{3}\\ ...


7

One useful package that I've been using for optimization modeling is ticdat, which is great for validating the input data and performing sanity and integrity checks. Because the data we receive in applications are almost never clean and a lot needs to be written to ensure they are correctly handled by either throwing an error or fixing what needs to be fixed ...


7

While it does not deliberately transform the problem before exporting it, using the LP file format means that double precision coefficients are being converted to character strings (and, in the process, truncated and/or rounded). So there will frequently be a little loss of precision, and sometimes that "little" loss of precision can turn into big ...


6

You obtain all vertices of a polytope using polymake. You can directly try the online version.


6

In Python, with pulp and networkx : import pulp import networkx as nx G = nx.Graph() # define your graph here #... # define the problem prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize) # define the variables x = pulp.LpVariable.dicts("x", G.nodes(), cat=pulp.LpBinary) z = pulp.LpVariable.dicts("z", G.edges(), ...


6

I am geophysics professor and have been solving scientific computing problems in Matlab since 2000. In the last ~8 years graduate students have been preferring to work in Python. I have the following observations: On a practical level Python is MUCH slower than Matlab. Code that my graduate students write is literally orders of magnitude slower than my ...


6

I can do 90% of my work with the following : pandas for data networkx for graphs pulp for linear programming modeling ipyleaflet for interactive maps line profiler for code profiling I use them extensively because they are: used by many others well documented maintained user friendly free open source robust


6

You could apply the following trick inside your objective function: x1 = min(x[1],x[2]) x2 = max(x[1],x[2]) Now x1 <= x2 automatically holds and you don't need the constraint. (Assuming you can live with <= instead of <).


6

Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous ...


6

I actually have quite a few points. As usual, things are not as clear cut. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model. For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related ...


6

In addition to profiler (mentioned by Kuifje), Python has quite a few unit testing libraries that can be used to test your application (unittest and pytest are both common). As in any commercial application, real-world OR applications should be flexible, maintainable and modularized. It is common to change some modelling objects (variables, constraints, etc),...


6

If you export the model, then by default, Cplex will export your original, unaltered model. When you solve a model, Cplex will, by default, first invoke a presolve,during which it will attempt to simplify and tighten your model, e.g. by removing redundant constraints, solving for logical implications, etc. As per this SO post, you can then also export the ...


6

Many many people know Excel and use Excel. So many OR projects start with some Excel spreadsheet. And that is why being able to read from and write to Excel is key. You may even start the project with the Excel solver. Moreover Excel is a common tool when companies choose plugin optimization instead of packages, custom or tailored optimization.


5

You can use SCIP with PYOMO easily. My way is: At first, use an executable SCIP version, it is available for the 7.0 version. After then giving the path of the executable to PYOMO, such as: solver = SolverFactory('scip', executable="./scip") It works. But I use BONMIN in same way.


5

SCIP used to be a bit challenging to set up with PYOMO as we needed to build the ASL interface. It's been a few years so I don't know if that's changed, but you can find a relevant discussion here. What might be easier would be to use Couenne, which is a deterministic global optimisation solver for MINLP and works out of the box with PYOMO. If you are a ...


5

You are just importing the pyomo.environ module while the tutorials probably use the from syntax. These variables are inside pyomo.environ so you have 3 alternatives: Import them explicitly from pyomo.environ import Var, NonNegativeReals Import them using a wildcard from pyomo.environ import * (this is considered an antipattern) Import the module (with an ...


5

Introduce a supersource node $s$, a supersink node $t$, arcs from $s$ to each source, and arcs from each sink to $t$. Arc $(s,i)$ has zero cost and capacity equal to supply[i]. Arc $(i,t)$ has zero cost and capacity equal to -supply[i]. All original nodes have supply zero, $s$ has supply equal to the sum of positive supplies, and $t$ has supply equal to ...


5

This is a tough problem indeed, but I am not sure about the "extremely NP-hard" part :). All problems which are NP-hard are...very hard. This looks like a multi-commodity flow problem, one commodity per depot. It is natural to decompose such a problem as follows. For each customer $v\in V$, for each commodity $k\in K$ we assume that the demand $D_{...


5

A TSP with a fixed starting point and no return to start, can be solved as an ordinary TSP with all the in-going arcs to the starting point having a cost of zero. That way the return to the starting point is "for free" and the TSP solver only focuses on the remaining part of the tour, giving you an optimal "open TSP".


5

Try: SetSolverSpecificParametersAsString("heuristics/completesol/maxunknownrate = 0.9") References: SCIP params SetSolverSpecificParametersAsString usage


5

You just seem to have hidden a long list of constraints of the form $(x_i=j) \Rightarrow \text{equalities}_{ij}$ Introduce a binary matrix $C_{ij}$ with $\sum_j C_{ij}= 1$ and $C_{ij} \Rightarrow \{x_{i} = j, \text{equalities}_{ij}\}$ To model the binary implication you can use big-M modelling, e.g. $-M(1- C_{ij})\leq x_{i} - j\leq M (1-C_{ij})$ and similar ...


5

Pushing @Erwin's idea further, I got faster solve times by instead introducing variables ry and qx: for j in b: for k in c: o += ry[j][k] == r[k] *(xsum(y[k][jj] for jj in b if jj <= j)) for j in b: for k in c: o += qx[j][k] == xsum(( xsum (q[i][k]* x[i][jj] for i in a )for jj in b if jj <=j)) for j in b: for k in c: ...


4

Economically speaking, if there is no cost of reprogramming your cutter (be it a CNC machine or a bearded handyman), there is no reason to go on and cut out all four rectangles from the next plywood sheet, if you only need one more. In this realistic scenario, you need a bit more control variables, than specified in the first attempt: 12 vs 3. If we allow ...


4

EDIT 1 I was able to replicate the issue and it turns out: There is a problem in the objective function. You can only have $1$, while you have a loop. Replace your objective function by prob += lpSum(y)-lpSum(x). Maybe the confusion came from the fact that with lpSum, if your coefficients are $1$, you don't have to write the variables as a dictionnary with ...


4

This is because you are trying to call z[(5,1)], while your variable is z[(1,5)]. Also u and v are mixed up in the last constraint. You can try: for v in g.nodes(): prob += pulp.lpSum([z[(u,v)] for u in g.neighbors(v) if (u,v) in z]) + pulp.lpSum([z[(v,u)] for u in g.neighbors(v) if (v,u) in z]) >= 2*(1-y[v])


4

Alternatively, just like in your previous question : for m in g.nodes(): prob += pulp.lpSum(z[(m,n)] for n in g.neighbors(m)) >= k*(1-y[m])


Only top voted, non community-wiki answers of a minimum length are eligible