Recent Questions - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2022-06-25T23:47:51Z https://or.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/8603 3 Additional resources for this type of problem formulation Bob Jeans https://or.stackexchange.com/users/5161 2022-06-25T14:28:50Z 2022-06-25T16:33:52Z <p>Im working on a problem with the following formulation:</p> <p><span class="math-container">$$min \sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij} \\ s.t. \sum_j x_{ij} = 1 \quad \forall i \in N\\ V_{ij} = \sum_{k \in N(i)} C_kx_{kj} \quad \forall i \in N, \forall j \in J \\ x_{ij} \in \{0,1\}, \quad V_{ij} \ge 0$$</span> where <span class="math-container">$C_k$</span> is a positive parameter, <span class="math-container">$J$</span> is small (ie <span class="math-container">$\{1,2,3\}$</span>). Every node <span class="math-container">$i$</span> is associated to every element in the set <span class="math-container">$J$</span>. For example, the objective would read something like: <span class="math-container">$V_{a,1}x_{a,1}+V_{a,2}x_{a,2}+V_{a,3}x_{a,3}+V_{b,1}x_{b,1}+...$</span></p> <p>Essentially, I have a dense connected graph with <span class="math-container">$N$</span> nodes, where <span class="math-container">$N(i)$</span> is the neighboring nodes of <span class="math-container">$i$</span>. The value of <span class="math-container">$V_{ij}$</span> is only relevant to the objective function if <span class="math-container">$x_{ij}$</span> takes a value of <span class="math-container">$1$</span>, however this means that <span class="math-container">$x_{ij}$</span> impacts its neighbors <span class="math-container">$V_{ij}$</span> value.</p> <p>I was hoping this model would be manageable for a solver, but it doesnt seem to be the case. The solver is unable to close the MIP gap (after ~1 hour of runtime), but it does look like its finding a good solution. I do recognize that there is a bilinear term in the objective, but the solver is able to break that on its own with relative ease. Also, I've broken the bilinear term but it doesnt make much of a difference, sadly. I have attempted to break the bilinear term by trying to approached (i) applying a new variable <span class="math-container">$z_{ij}$</span> that is either <span class="math-container">$0$</span> or <span class="math-container">$V_{ij}$</span> depending on the value of <span class="math-container">$x_{ij}$</span>, AND (ii) by changing the equation for <span class="math-container">$V_{ij}$</span> directly so it either takes a value of <span class="math-container">$0$</span> or the relevant value.</p> <p>Is anyone aware of this type of formulation and where I can read more about it? Or any ideas on model improvements? Thanks!</p> https://or.stackexchange.com/q/8602 2 Transfer an integer model to binary Laura https://or.stackexchange.com/users/9883 2022-06-25T08:03:44Z 2022-06-25T16:20:28Z <p>I have a minimization problem with integer variables and would like to transform it to binary variables. The problem is, that my objective is to minimize the overall waiting time, which consists of number of passengers*waiting time.</p> <p>Current problem: min TWT = sum(l,la,h) w(l,la,h)*u(l,la,h)<br /> w and u are both integers</p> <p>If I consider w(l,la,h,t) to be binary with a time index (1 if waiting time is t, 0 otherwise), I don't know how capture the weight t. Multiplying by t does not work in my model.</p> <p>I am thankful for any suggestions.</p> https://or.stackexchange.com/q/8599 2 Getting all active constraints of an LP from Cplex Elena https://or.stackexchange.com/users/9588 2022-06-24T12:38:48Z 2022-06-24T13:09:08Z <p>I was wondering if it is possible to get the active constraints of a linear program from the Python API of Cplex? Or do I have to go through the constraints one by one and check if they bind with equality for the current solution?</p> https://or.stackexchange.com/q/8597 2 Difference between constraint formulation and performance Mike https://or.stackexchange.com/users/9830 2022-06-24T12:01:51Z 2022-06-24T19:07:10Z <p>I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.<br /> At first: <span class="math-container">$$a,b,c \in \{0,1\} \\ a\cdot b = c \tag{1}$$</span> Is it a quadratic constraint because of the multiplication with two variables.<br /> I try to model the logical equation <span class="math-container">$a \land b = c$</span> and wonder about the performance of equation 1 or 2 (<a href="https://msi-jp.com/xpress/learning/square/10-mipformref.pdf" rel="nofollow noreferrer">linearization of AND-Constraint, Chapter 2.5</a>). <span class="math-container">\begin{align} c &amp;\le a \\ c &amp;\le b \\ c &amp;\ge a+b-1 \tag{2} \end{align}</span> Which one should I use and why (please considering performance)?</p> <p>Second:<br /> What is the difference between equation 3 and 4 for the logical equation <span class="math-container">$a = 1 \rightarrow b = c$</span> with <span class="math-container">$a \in \{0,1\}; b,c \in \mathbb{N}$</span>? From a logical/mathematical point of view, I do not see anyone. <span class="math-container">$$a \cdot b = a\cdot c \tag{3}$$</span></p> <p><span class="math-container">\begin{align} b-a\cdot M &amp;= c-a\cdot M \tag{4} \end{align}</span></p> <p>Summary of the questions:</p> <ol> <li>Is there a performance issue between <span class="math-container">$(1)$</span> and <span class="math-container">$(2)$</span>?</li> <li>Which equation (<span class="math-container">$(3)$</span> or <span class="math-container">$(4)$</span>) should I use and why?</li> </ol> <p>If you know a good resource that explains these basics, please let me know.</p> https://or.stackexchange.com/q/8594 10 Integer column generation without branch & price Curious https://or.stackexchange.com/users/9880 2022-06-24T07:47:00Z 2022-06-24T12:01:30Z <p>Consider the following situation. I have an integer program which I want to solve using column generation. After a suitable decomposition, the master problem has decision variables that select the columns to use in order to satisfy some constraint. Unlike in ordinary Dantzig-Wolfe (DW) reformulation, here the MP variables have to be integer. This suggests using Branch and Price where (DW) is used to solve the LP relaxations at the nodes and one adopts a suitable branching strategy to recover integrality.</p> <p>Assume now that I do the following:</p> <ul> <li>I solve the LP relaxation of MP using DW</li> <li>I retain all the columns generated in the process</li> <li>I solve MP again as an integer program using those columns</li> </ul> <p><strong>My question is</strong>: Does this approach provide the optimal solution to the original problem, or it is just a heuristic? And why?</p> https://or.stackexchange.com/q/8593 4 Geometric Programming with Simple Affine Equality Constraint Apprentice https://or.stackexchange.com/users/5005 2022-06-24T07:43:43Z 2022-06-24T14:43:56Z <p>Consider a <a href="https://web.stanford.edu/%7Eboyd/papers/pdf/gp_tutorial.pdf" rel="nofollow noreferrer">Geometric Program (GP)</a>, <span class="math-container">$$\begin{array}{cl} \operatorname{minimize} &amp; f_{0}(x) \\ \text { subject to } &amp; f_{i}(x) \leq 1, \quad i=1, \ldots, m, \\ &amp; g_{i}(x)=1, \quad i=1, \ldots, p, \end{array}$$</span> where <span class="math-container">$f_i$</span> are posynomial functions, <span class="math-container">$g_i$</span> are monomials, and <span class="math-container">$x$</span> is the optimization variable.</p> <p>I have problems including the simple equality constraint <span class="math-container">$Ax - b = 0$</span>, for some <span class="math-container">$A$</span> and <span class="math-container">$b$</span>, into the GP formulation. For example, when I formulate the problem in CVX the problem is not DGP-compliant since this equality violates the disciplined GP rules. This is because standard GPs only allow monomial equality constraints in its formulation, and <span class="math-container">$Ax - b$</span> can be interpreted as a posynomial.</p> <p>Is there any workaround to this? I tried to relax the constraint as <span class="math-container">$Ax \leq b$</span> (since polynomials are allowed in inequality constraints) but strangely CVX still raise a DGP error.</p> https://or.stackexchange.com/q/8592 1 How to make unconstrained variables non-negative (as in excel solver) in AMPL? Don Quijote https://or.stackexchange.com/users/9875 2022-06-23T14:28:55Z 2022-06-23T23:53:52Z <p>This is a sequencing problem.</p> <p>I've got this variables</p> <pre><code>var z0{i in jobs} binary; var z{i in jobs, j in jobs : i &lt;&gt; j} binary; var w{i in jobs, j in jobs : i &lt;&gt; j}; var o{i in jobs}; </code></pre> <p>i and j come from the same set, so z0i is 1 if it's the first job in the sequence, 0 otherwise. zij is 1 if j is after i, 0 otherwise.</p> <p>I want to calculate w and o with this:</p> <pre><code>subject to rnueve {i in jobs, j in jobs : i &lt;&gt; j}: (x[j]-f[i]) - 10000 * (1 - z[i,j]) = w[i,j]; subject to rdiez {i in jobs}: x[i] - 10000 * (1 - z0[i]) = o[i]; </code></pre> <p>The thing is, I need to put the M in from of it so when j is not after i, the variables o and w are super negative.</p> <p>After that, I need to make those negative values equal to zero, but I don't know how without having to make the solution nonlinear.</p> <p>In excel's solver, there's a button that does this. You mark: Make unconstrained variables non-negative. And this does what I described.</p> <p>If I try to make w and o &gt;= 0 I get an infeasible solution because, with the big M, there is no posible way to find a solution with w and o being non negative.</p> <p>What i want to do is get a negative value, and then if it's actually negative, make it zero.</p> <p>Thanks in advance.</p> https://or.stackexchange.com/q/8590 2 Np-hard sequencing or packing problems with total ordering between elements prakash gawas https://or.stackexchange.com/users/899 2022-06-22T19:44:56Z 2022-06-22T23:28:12Z <p>I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything. For example there is cost that needs to be payed if some job finishes earlier than others.</p> <p>Normally with total ordering problems like minimum makespan scheduling are easy to solve as there is no flexibility in this case and task orders are fixed.</p> https://or.stackexchange.com/q/8588 2 Reformulating a constraint that is non linear? baxbear https://or.stackexchange.com/users/2989 2022-06-22T15:56:35Z 2022-06-22T16:06:53Z <p>I created the following constraint (missing what exists in this context means)</p> <pre><code>For all a in A there exists a b in B so that for all c in C it holds that a variable x(a, b + c) is equal to a parameter m(a, c) </code></pre> <p>short:</p> <p><span class="math-container">$$\forall a \in A, \exists b \in B, \forall c \in C: x(a,b+c)=m(a,c)$$</span></p> <p>What this constraint is trying to do is to ensure that for a given object <code>a</code> the values of a given tuple <code>m(a,c)</code> (both binary tuples) can be found in the same order. Of course that would mean that only <code>|B|-1</code> constraints have to be true which is a problem (that I did not notice before). Can this be reformulated without the <code>exists</code> clause?</p> <p>Therefore, <code>m(a,c)</code> is the given parameter of a smaller tuple for some object <code>a</code>. The constraint ensures that x for an object <code>a</code> starting at some position <code>b</code> contains the values of m(a,c) in the order of <code>m(a,c)</code>. The tuples <code>m(a,c)</code> all have different sizes.</p> <p>Therefore, with this and additional constraints I tried to solve a knapsack problem in which a set of different tuple have to be placed within a larger tuple. The tuple contains binary values representing <code>1</code> the position is used <code>0</code> the position is unused. Hence, if a position is not used (0) a different tuple can use it if it doesn't gets in conflict with the other assignments:</p> <p><span class="math-container">$$\forall b\in B: \sum_{a\in A} x(a,b)\leq 1$$</span></p> <p>it doesn't matter whether for a object <code>a</code> in x positions <code>b</code> are marked as used even so they are not. It only matters to find whether for a tuple of a certain size the other tuples can be somehow fitted into.</p> <p>Can the first constraint somehow reformulated to be linear? If not, what is the best I could do?</p> https://or.stackexchange.com/q/8586 2 Linearize function user9867 https://or.stackexchange.com/users/9867 2022-06-22T10:42:55Z 2022-06-22T12:19:58Z <p>I have a facility location problem with a non-linear objective;</p> <ul> <li>There are fixed costs <span class="math-container">$S_j$</span> to opening facility <span class="math-container">$j$</span></li> <li><span class="math-container">$Y_j$</span> is a binary, <span class="math-container">$1$</span> if facility <span class="math-container">$j$</span> is opened, <span class="math-container">$0$</span> otherwise</li> <li><span class="math-container">$D_j$</span> is the number of products that will be gathered at facility <span class="math-container">$j$</span></li> <li>It is cheaper to assign more products to an open facility as fixed costs can be spread. Therefore, there is a negative slope of <span class="math-container">$-a\cdot D_j$</span> when a facility is open. Indicating that when more products are assigned to an open collection point, this will be deducted from the fixed cost.</li> </ul> <p>This gives the objective function <span class="math-container">$$S_j \cdot Y_j - a \cdot D_j \cdot Y_j$$</span></p> <p>How do I linearize this to create a linear programming problem?</p> https://or.stackexchange.com/q/8584 2 multi stage stochastic programming algorithm mahgol https://or.stackexchange.com/users/9865 2022-06-21T19:34:19Z 2022-06-22T09:15:18Z <p>I have a multi-stage stochastic programming model. I have 3 groups of variables: the first group takes values at the beginning of the planning horizon before the first realization and does not change until the end of the planning horizon and has no t index (they are binary and continuous), the second option is “here and now” variables that before each realization Are taken value and are continuous, the third group are “wait and see” variables that take value after each realization (binary and continuous). The model is SMINLP. I converted it to SMILP through linearization and solved it by CPLEX solver with generating a small number of scenarios . I want to consider a continuous distribution for the stochastic parameter and generate a large number of scenarios by sampling and run an algorithm for it. nested benders decomposition or progressive hedging algorithms are more efficient for this model? If anyone has experience, thank you in advance for your help.</p> https://or.stackexchange.com/q/8581 -3 Testing Varying Parameters With the Same Script [closed] Routine Ma https://or.stackexchange.com/users/9746 2022-06-20T13:28:11Z 2022-06-22T12:21:16Z <p>As the title suggests, I would like to test different values of parameters with the same code in C++.</p> <p>For example, one of the parameters is: <code>#define α 0.5</code>. I would like to run the same code, but with different values of <code>α</code>, like <code>#define α 0.6</code>. How can I do that?</p> https://or.stackexchange.com/q/8579 3 Practical, Short example of Mixed Integer Conic Program worldsmithhelper https://or.stackexchange.com/users/4777 2022-06-19T20:42:57Z 2022-06-19T22:49:31Z <p>Mixed Integer Conic Programs is a family of Mixed Integer Programs which are convex in all non integer variables. I am giving presentation on Mixed Integer technology. A large part of the presentation will be about MILP, it's tricks and common problem structures. I will also make people aware of MINLP by giving a practical non-convex MINLP. I aim to do the same with a convex MINLP. Is someone aware of an easy to explain MIP using a Second-order, Rotated second-order, Positive semidefinite or Primal exponential which has a practical application?</p> <p> It should not involve power networks, trajectory optimisation and ideally fit on a slide. Why the cone is needed should be obvious from the problem description.</p> https://or.stackexchange.com/q/8578 2 Defining a highly non-linear function of integer variables Johnthemathematician https://or.stackexchange.com/users/9857 2022-06-19T11:46:32Z 2022-06-20T14:38:39Z <p>I have a complicated non-linear objective function of positive integer variables subject to linear constraints:</p> <p><span class="math-container">$\mathop {Min}\limits_{\underline x} f(\underline x)$</span></p> <p>s.t.</p> <p><span class="math-container">$A\underline x\leq \underline b$</span></p> <p><span class="math-container">$\underline x \in \mathbb{Z}$</span>, <span class="math-container">$\underline x \geq 0$</span>. <span class="math-container">$f(\underline x)=g(\underline x)+h(\underline x)+p(\underline x)+q(\underline x)$</span>.</p> <p>For the small version of the problem where A is 17×48, <span class="math-container">$g$</span> is defined as follows.</p> <p><span class="math-container">\begin{equation}\label{Ca1} C_a^1=\frac{1}{\frac{1}{\sum_{i=1}^{4} x_{i}C_i+(3-\sum_{i=1}^{4} x_{i})C_5}+\frac{1}{\sum_{i=5}^{8} x_{i}C_i+(3-\sum_{i=5}^{8} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Ca2} C_a^2=\frac{1}{\frac{1}{\sum_{i=9}^{12} x_{i}C_i+(3-\sum_{i=9}^{12} x_{i})C_5}+\frac{1}{\sum_{i=13}^{16} x_{i}C_i+(3-\sum_{i=13}^{16} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Cb1} C_b^1=\frac{1}{\frac{1}{\sum_{i=17}^{20} x_{i}C_i+(3-\sum_{i=17}^{20} x_{i})C_5}+\frac{1}{\sum_{i=21}^{24} x_{i}C_i+(3-\sum_{i=21}^{24} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Cb2} C_b^2=\frac{1}{\frac{1}{\sum_{i=25}^{28} x_{i}C_i+(3-\sum_{i=25}^{28} x_{i})C_5}+\frac{1}{\sum_{i=29}^{32} x_{i}C_i+(3-\sum_{i=29}^{32} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Cc1} C_c^1=\frac{1}{\frac{1}{\sum_{i=33}^{36} x_{i}C_i+(3-\sum_{i=33}^{36} x_{i})C_5}+\frac{1}{\sum_{i=37}^{40} x_{i}C_i+(3-\sum_{i=37}^{40} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Cc2} C_c^2=\frac{1}{\frac{1}{\sum_{i=41}^{44} x_{i}C_i+(3-\sum_{i=41}^{44} x_{i})C_5}+\frac{1}{\sum_{i=45}^{48} x_{i}C_i+(3-\sum_{i=45}^{48} x_{i})C_5}} \end{equation}</span></p> <p><span class="math-container">\begin{equation}\label{Ca} C_a=C_a^1+C_a^2 \end{equation}</span> <span class="math-container">\begin{equation}\label{Cb} C_b=C_b^1+C_b^2 \end{equation}</span> <span class="math-container">\begin{equation}\label{Cc} C_c=C_c^1+C_c^2 \end{equation}</span> <span class="math-container">\begin{equation}\label{g} g(\underline{x})=(C_a+C_b+C_c)\sqrt{[C_a-\frac{1}{2}(C_b+C_c)]^2+(C_b-Cc)^2} \end{equation}</span></p> <p>where <span class="math-container">$C_1$</span>...<span class="math-container">$C_{48}$</span> are constant and known. <span class="math-container">$h$</span>, <span class="math-container">$p$</span> and <span class="math-container">$q$</span> are as complicated.</p> <p>In Matlab,each of <span class="math-container">$g,h,p,q$</span> is defined by a function which employs various other functions which contain many loops for different elements of <span class="math-container">$\underline x$</span>.</p> <p>Size of <span class="math-container">$A$</span> is in the order of 100 <span class="math-container">$\times$</span> 2000. I tried first to solve the problem in Matlab, using the <em>ga</em> function. Unfortunately, the solutions obtained for several runs never satisfied the constraints.</p> <p>I have successfully implemented an algorithm in Matlab where in each iteration a random solution that satisfies the constraints is generated and <span class="math-container">$f(\underline x)$</span> is evaluated using multiple functions defined. Using a large number of iterations, say 1e6, I could find a reasonable yet not a globally optimal solution. My next plan was to use the CPLEX solution pool. For small <span class="math-container">$A$</span> and <span class="math-container">$b$</span>, it was possible to have all the solutions of inequality <span class="math-container">$A\underline x\leq \underline b$</span>, import these solutions as a CSV file in Matlab and evaluate them one by one so that the least objective function gives the globally optimal solution. This, however, does not work for actual <span class="math-container">$A$</span> and <span class="math-container">$b$</span> which make the CPLEX out of memory. My idea was to use an incumbent filter so that non-optimal solutions of <span class="math-container">$A\underline x\leq \underline b$</span> get discarded and therefore the memory problem gets resolved. For example the solutions for which <span class="math-container">$f(\underline x)&gt;c$</span>, where constant <span class="math-container">$c$</span> is heuristically defined, can be discarded. My question is:Is there a way to define my complicated objective function in GAMS environment the way I did in Matlab? Have you faced a similar situation which can be referred to so that I have a clue?</p> https://or.stackexchange.com/q/8574 3 Optimization software for real-valued functions/constraints of complex arguments Dan Doe https://or.stackexchange.com/users/9847 2022-06-17T09:32:22Z 2022-06-18T17:12:37Z <p>I am interested in an optimization problem of the form <span class="math-container">$$\min_{\boldsymbol z} \max_j \vert f_j(\boldsymbol z) \vert = \min_{\boldsymbol z} \Vert f_j(\boldsymbol z) \Vert_\infty.$$</span> Here, the optimization/decision variables are <span class="math-container">$\boldsymbol z \in \mathbb C^{N}$</span> and <span class="math-container">$f_i: \mathbb C^N \to \mathbb C$</span>.</p> <p>The <span class="math-container">$f_j$</span> are essentially polynomials in <span class="math-container">$\lambda_j \in \mathbb C$</span> <span class="math-container">$$f_j(\boldsymbol z ) = \prod_{k=1}^N \big(1 - z_k \lambda_j\big).$$</span></p> <p>To provide some more context, I am essentially trying to optimize the common roots of complex polynomials. Write the polynomial <span class="math-container">$p(\lambda)$</span> with <span class="math-container">$p(0) = 1$</span> as <span class="math-container">$$p(\lambda) = \prod_{k=1}^N \bigg(1 - \frac{ \lambda}{\tilde z_k} \bigg)$$</span> where <span class="math-container">$\tilde z_k$</span> are the roots of the polynomial. For <span class="math-container">$z_k := 1/\tilde z_k$</span> you obtain the representation above.</p> <p>In principle, one has also to enforce that the roots come in complex-conjugated pairs which would give a linear constraint like <span class="math-container">$$A \boldsymbol z = \boldsymbol 0.$$</span></p> https://or.stackexchange.com/q/8573 4 Subtour elimination implementation (DFJ) using Python (PULP). While loop never exits Parseval https://or.stackexchange.com/users/4222 2022-06-17T09:29:47Z 2022-06-17T15:26:32Z <p>The simple test problem I'm trying to implement is</p> <p><span class="math-container">\begin{align} \min &amp;\quad c_{ij}x_{ij} \\ \text{s.t} &amp;\quad \\ &amp;\quad \sum_{j\in N}x_{ij} = 1, \quad i\in N\\ &amp;\quad \sum_{i\in N}x_{ij} = 1, \quad j\in N\\ &amp;\quad x_{ii} = 0, \quad i\in N\\ &amp;\quad \sum_{i\in S}\sum_{j\in S, \ j\neq i} x_{ij} \leq |S|-1, \quad \forall S \subset N, 2\leq |S| \leq n-1 \\ &amp; \quad x_{ij}\in\{0,1\}, \quad i,j\in{N} \end{align}</span></p> <p>where <span class="math-container">$N={1,...,n}$</span> is number of locations and <span class="math-container">$S$</span> is the set of sub-tours. I have the following locations with their coordinates and the corresponding distance matrix for each pair of locations named <code>locations_df</code> and <code>dist_mat</code> respectively.</p> <p>I've followed <a href="https://medium.com/swlh/techniques-for-subtour-elimination-in-traveling-salesman-problem-theory-and-implementation-in-71942e0baf0c" rel="nofollow noreferrer">this article</a> (<a href="https://github.com/Ayaush/TSP-ILP/blob/main/Subtour%20elimination%20in%20TSP.ipynb" rel="nofollow noreferrer">github-link</a>) and I managed to correctly implement the MTZ version, however I'm running into troubles when trying to implement the DFJ method of sub-tour elimination. More specifically, the while loop (NOT any of the while loops in the function <code>get_plan</code> but further below, the last one) below never exits and I can't figure out why the size of sub-tour list never goes to 1 in order to exit the while loop. I've spent quite a lot of time trying to debug this and I'd appreciate any help.</p> <p>The code below should be completely reproducible, just copy and paste. Note that <code>pip install pulp</code> is required.</p> <pre><code>import pulp import pandas as pd import numpy as np import copy location_df = pd.DataFrame({'Location': ['Depot','LL716','LL384','LR59','LL701','LL866','LR830','LL1034','LR80','LR220','LL804'], 'x': [0.00,140.21,76.48,6.37,133.84,172.07,159.33,203.94,12.75,38.24,159.33], 'y': [0.00,30.62,0.00,68.90,74.00,5.10,76.55,25.52,40.83,71.45,10.21]}) N = len(location_df) dist_mat = np.array([[ 0. , 170.83, 76.48, 75.27, 207.84, 177.17, 235.88, 229.46, 53.58, 109.69, 169.54], [170.83, 0. , 94.35, 172.12, 49.75, 67.58, 65.05, 86.69, 137.67, 142.8 , 57.39], [ 76.48, 94.35, 0. , 139.01, 131.36, 100.69, 159.4 , 152.98, 104.56, 109.69, 93.06], [ 75.27, 172.12, 139.01, 0. , 147.72, 229.5 , 170.66, 240.95, 37.01, 54.67, 211.65], [207.84, 49.75, 131.36, 147.72, 0. , 107.13, 38.09, 118.58, 156.82, 113.3 , 89.28], [177.17, 67.58, 100.69, 229.5 , 107.13, 0. , 84.19, 62.49, 195.05, 200.18, 28.05], [235.88, 65.05, 159.4 , 170.66, 38.09, 84.19, 0. , 95.64, 184.86, 136.24, 66.34], [229.46, 86.69, 152.98, 240.95, 118.58, 62.49, 95.64, 0. , 206.5 , 211.63, 80.34], [ 53.58, 137.67, 104.56, 37.01, 156.82, 195.05, 184.86, 206.5 , 0. , 58.67, 177.2 ], [109.69, 142.8 , 109.69, 54.67, 113.3 , 200.18, 136.24, 211.63, 58.67, 0. , 182.33], [169.54, 57.39, 93.06, 211.65, 89.28, 28.05, 66.34, 80.34, 177.2 , 182.33, 0. ]]) ##################### Solve model using the DFJ subtour elimination # find all sub-tours in the solution def get_plan(r0): r = copy.copy(r0) route = [] while len(r) != 0: plan = [r] del (r) l = 0 while len(plan) &gt; l: l = len(plan) for i, j in enumerate(r): if plan[-1] == j: plan.append(j) del (r[i]) route.append(plan) return(route) model = pulp.LpProblem('tspDFJ',pulp.LpMinimize) #define variable x = pulp.LpVariable.dicts(&quot;x&quot;,((i,j) for i in range(N) \ for j in range(N)), \ cat='Binary') #set objective model += pulp.lpSum(dist_mat[i][j] * x[i,j] for i in range(N) \ for j in range(N)) # st constraints for i in range(len(location_df)): model += x[i,i] == 0 model += pulp.lpSum(x[i,j] for j in range(N)) == 1 model += pulp.lpSum(x[j,i] for j in range(N)) == 1 status = model.solve() route = [(i,j) for i in range(N) \ for j in range(N) if pulp.value(x[i,j]) == 1] S = get_plan(route) subtour = [] #Check if we got subtours, if we do, we while len(S) != 1: for i in range(len(S)): #print(S[i]) model += pulp.lpSum(x[S[i][j], S[i][j]] \ for j in range(len(S[i])) if j!=i) &lt;= len(S[i]) - 1 status = model.solve() route = [(i,j) for i in range(N) \ for j in range(N) if pulp.value(x[i,j]) == 1] S = get_plan(route) subtour.append(len(S)) print(&quot;-----------------&quot;) print(status,pulp.LpStatus[status],pulp.value(model.objective)) print(S) print(&quot;no. of times LP model is solved = &quot;, len(subtour)) print(&quot;subtour log (no. of subtours in each solution))&quot;, subtour) </code></pre> https://or.stackexchange.com/q/8572 1 Converting quadratic constrains to linear constraint Mike https://or.stackexchange.com/users/9830 2022-06-16T23:05:45Z 2022-06-16T23:05:45Z <p>I try to convert a quadratic constraint to a linear one: <span class="math-container">$$w_j = \sum w_\text{j,i} \\ w_\text{j,i} = \frac{w_j}{D} \times u \\ w_j,D,u \in \mathbb{N} \\$$</span> The values for <span class="math-container">$w_j$</span> and <span class="math-container">$D$</span> are constant and does not change.<br /> In fact, I try to divide the value of <span class="math-container">$w_j$</span> to pieces, defined by <span class="math-container">$D$</span>. For example: <span class="math-container">$D = 4$</span> and <span class="math-container">$w_j = 100$</span> with <span class="math-container">$w_\text{j,0},w_\text{j,1} \in {0,25,50,100}$</span>.</p> <p>At first: Is there a way to express such a case with linear constraints?<br /> At second: Is there a rule how to convert quadratic to linear constraints?</p> https://or.stackexchange.com/q/8564 3 Can a TSP K-OPT operator be completed with a sequence of 2-OPT moves? jkschin https://or.stackexchange.com/users/9794 2022-06-15T19:38:52Z 2022-06-15T21:50:48Z <p>This seems intuitive and is likely correct, but I'm looking for a paper or perhaps a more thorough proof on how a K-OPT move is equivalent to a sequence of 2-OPT moves. Or if this is wrong, something that shows why this is wrong with a counter example.</p> <p>For reference, there's a blog post on how a 3-OPT is a sequence of 2-OPT moves <a href="https://tsp-basics.blogspot.com/2017/03/3-opt-move.html" rel="nofollow noreferrer">here</a></p> https://or.stackexchange.com/q/8563 -1 How can we evaluate metaheuristics statistically? charafeddine https://or.stackexchange.com/users/9833 2022-06-15T17:32:30Z 2022-06-16T00:56:35Z <p>I have enhanced the PSO metaheuristic. Now, for my experimentation, I want to use a statistical test like the Wilcoxon test (but I didn't know why researchers do Wilcoxon test? And what is the objective of using the Wilcoxon test?). Also, I want to display the boxplot to show the obtained fitness value for each algorithm I compare with over 15 executions(But I didn't know What is the objective to display the boxplot).</p> <p>Note: I am not familiarised with operations research so please give details in the comments</p> https://or.stackexchange.com/q/8561 3 gurobi bigM constraint vs. epsilon Mike https://or.stackexchange.com/users/9830 2022-06-15T14:49:22Z 2022-06-15T15:53:08Z <p>I am new to mathematical programming and I am trying to implement case specific constrains in Gurobi with Python.</p> <p>I am wondering about how I can implement my constraints in the fastest or most common way.</p> <p>There are three variables: <span class="math-container">$$w_i,w_j \in \mathbb{N}, y_\text{i,j} \in \{0,1\}$$</span> The indices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> referes to fiction tasks since this model takes part of a task scheduling problem. Variable <span class="math-container">$w$</span> is a weight of the task and <span class="math-container">$y$</span> shows if task <span class="math-container">$i$</span> precedes <span class="math-container">$j$</span>. So there are some other constraints to provide some preceding rules.</p> <p>I need to implement different constraints (let's say <span class="math-container">$C_1, C_2, C_3$</span>) depending to those variables:<br /> <span class="math-container">$$1: (w_i &gt; w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_1 \\ 2: (w_i = w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_2 \\ 3: (w_i &lt; w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_3$$</span></p> <p>To implement this constraint I need introduce new binary variables to the model (let's say <span class="math-container">$a_1,a_2,a_3$</span>) wich are only equal <span class="math-container">$1$</span>, when the refered case is true. Since Gurobi does not implement strict less or greater operators, <a href="https://support.gurobi.com/hc/en-us/articles/4414392016529-How-do-I-model-conditional-statements-in-Gurobi-" rel="nofollow noreferrer">I need to model a bigM constraints</a> for the variables <span class="math-container">$a$</span>.</p> <p><span class="math-container">$$w_i \ge w_j + \epsilon - M(1-a_1) \\ w_i \le w_j + M \times a_1 \\ a_1 \in {0,1} \\ \epsilon &lt;&lt; w_i \tag{1}$$</span></p> <p>Since there is a constraint that says, that either <span class="math-container">$y_\text{i,j}$</span> or <span class="math-container">$y_\text{j,i}$</span>, but not both, are equal 1, I plan to implement a constraint for each case with a new binary variable <span class="math-container">$b$</span> to represent the logical condition: <span class="math-container">$$b_1 = a_1 \times (y_\text{i,j} + y_\text{j,i})$$</span></p> <p>Finally, I am able to implement each case with an indicator constraint like <span class="math-container">$b_x \rightarrow C_x; x\in {1,2,3}$</span></p> <p>At first, I am wondering if the second equation of EQ:1 can also expressed with epsilon instead of M as <span class="math-container">$w_i \le (w_j - \epsilon) \times a_1$</span>.</p> <p>What is the difference?</p> <p>Second, Is this the correct way to implement a problem like this or is there a better way?</p> https://or.stackexchange.com/q/8559 3 Multiprocessor Scheduling Problem: How to modify some constraints after variable changing? Alexandre Frias https://or.stackexchange.com/users/1252 2022-06-15T07:22:49Z 2022-06-15T21:42:20Z <p>I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning):</p> <p>Given <span class="math-container">$n$</span> tasks, with times <span class="math-container">$\{t_i\}_{i\in I_n}$</span>, and <span class="math-container">$m$</span> machines. The goal is to assign each task to a machine such that the maximum time to finish all tasks is minimized. (<span class="math-container">$I_n = \{1,2,3,...,n\}$</span>)</p> <p>It is possible to build a mathematical model for Multiprocessor Scheduling Problem as follows:</p> <p><span class="math-container">\begin{eqnarray} \min &amp;&amp; \label{b1} T \\ \mbox{suj. a} &amp;&amp; \label{b2} \sum_{i=1}^{n}t_i x_{i,j} \leq T, \quad \forall j\in I_m \\ &amp;&amp; \label{b3} \sum_{j=1}^{m} x_{i,j} = 1, \quad \forall i\in I_n \quad (*)\\ &amp;&amp; \label{b4} \sum_{i=1}^{n} x_{i,j} \geq 1, \quad \forall j\in I_m \quad (**)\\ &amp;&amp; \label{b5} x_{i,j} \in\{0,1\}, \quad \forall (i,j)\in I_n\times I_m\\ &amp;&amp; \label{b6} T \in \mathbb{R}_{+} \end{eqnarray}</span></p> <p>Where the variable <span class="math-container">$x_{i,j}$</span> indicates if the task <span class="math-container">$i$</span> is assigned in the machine <span class="math-container">$j$</span>, or not. Assume that we change the variable <span class="math-container">$x_{i,j}$</span> by <span class="math-container">$z_{i,k}$</span> which means the tasks <span class="math-container">$i$</span> and <span class="math-container">$k$</span> are both assigned in the same machine (<span class="math-container">$z_{i,i}=1$</span>, task <span class="math-container">$i$</span> is alone in a machine). In another words,</p> <p><span class="math-container">$$z_{i,k}=\sum_{j=1}^{m} x_{i,j}.x_{k,j}, \quad \forall (i,k): 1\leq i\leq k \leq n$$</span></p> <p>I know how to ensure the transitivity relationship and calculate the total time in each machine</p> <p><span class="math-container">$$z_{ij} + z_{jk} - z_{ik}\leq 1, \quad \forall (i,j,k): 1\leq i&lt;j&lt;k\leq n$$</span> <span class="math-container">$$\sum_{i=k}^{n}t_i z_{i,k} \leq T$$</span></p> <p>I do not know how to translate (*) and (**). I am thinking about how to do it. Thank you for any tip you share with me.</p> https://or.stackexchange.com/q/8558 0 How to model history-dependent dynamic program? Amin https://or.stackexchange.com/users/139 2022-06-15T04:48:46Z 2022-06-19T16:07:49Z <p>Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history, or all information gathered in a time window. My first question is if this model can be considered a Markov decision process? In an MDP, the state of the current time should be based on the state of the problem in the former time period. Here, this is true but we have gathered all information.</p> <p>My second question is what are the general approaches to solve history-dependent dynamic programs? If we summarize information as a probability distribution, we would lose the exact information and our results will be suboptimal. I would be thankful if you can share some references for discrete and continuous-time problems.</p> <p><strong>Note</strong>: I asked this question in the following group, but I don't know if it is possible to transfer the question to this group or not. <a href="https://math.stackexchange.com/questions/4270848/how-to-model-history-dependent-dynamic-program">This link</a></p> https://or.stackexchange.com/q/8556 3 Disjunctive Constraint , Using Binary Variable to Replace a If or condition Danish Shaikh https://or.stackexchange.com/users/9820 2022-06-14T22:44:39Z 2022-06-14T23:20:06Z <p>I am trying to use a binary variable based on an inequality. The value of binary variable <span class="math-container">$q$</span> is 1 or 0 based on the following equation.</p> <blockquote> <p>[ <span class="math-container">$q$</span> = <span class="math-container">\begin{cases} 0,&amp; \text{if } b \geq \pi ,\\ 1, &amp; \text{otherwise} \end{cases}</span></p> </blockquote> <p>Here, b and <span class="math-container">$\pi$</span> are real numbers. Sample value b = 20 , <span class="math-container">$\pi$</span> = 30.</p> <p>I have tried to represent this by:</p> <p><span class="math-container">\begin{equation} q \geq \dfrac { (\pi - b )} {M} \end{equation}</span></p> <p><span class="math-container">\begin{equation} q \leq 1 + \dfrac { (\pi - b )} {M} \end{equation}</span></p> <p>By using these two equations I am able to cover the cases for when <span class="math-container">$b &gt; \pi$</span> and when <span class="math-container">$b &lt; \pi$</span>. Unfortunately I am unable to set <span class="math-container">$q$</span> as 0 when <span class="math-container">$b=q$</span> without violating other conditions.</p> https://or.stackexchange.com/q/8550 6 Python vs. compiled languages in OR research using metaheuristics Leon Lan https://or.stackexchange.com/users/2886 2022-06-14T15:10:27Z 2022-06-16T17:38:14Z <p>In many articles that use metaheuristics to solve optimization problems, the programming language of choice is C++. For example, the following two articles present state-of-the-art metaheuristics to solve the Capacitated Vehicle Routing Problem and are implemented in C++: <a href="https://pubsonline.informs.org/doi/abs/10.1287/trsc.2021.1059?casa_token=qfY8kgSxjT4AAAAA:Jq8ud5gC60Jz0QKbszOv3fGpBhMuuT8wAHY47Fe09-kHXn0OZoFotiP7rlE5oQ-mRJm6X_BT_zLp" rel="nofollow noreferrer">Accorsi and Vigo (2021)</a> and <a href="https://www.sciencedirect.com/science/article/abs/pii/S030505482100349X?via%3Dihub" rel="nofollow noreferrer">Vidal (2022)</a>.</p> <p>I have yet to find a paper that uses Python to implement a metaheuristic for routing or scheduling problems. As I recently started my PhD in this field and I only have experience with programming in Python, I'm wondering whether it's even acceptable to use Python for my research.</p> <p>Assuming that the algorithmic aspects of my code are efficient (e.g., implementing local search methods in the best-known time complexity, using efficient data structures), would it hurt my chances to publish in top quality journals if I use Python in my research instead of C++ or another compiled language?</p> <p>Although I have not read a lot of literature on exact methods, I believe this issue is less prevalent because most people make use of commercial solvers such as CPLEX and Gurobi. But if my question also applies in this case, please feel free to share your thoughts on this as well.</p> https://or.stackexchange.com/q/8546 2 Approximate Speed-Up With Increasing Cores? Ralph Asher https://or.stackexchange.com/users/3958 2022-06-14T13:01:41Z 2022-06-14T15:43:30Z <p>First off: I totally understand if &quot;it depends&quot; is the only feasible solution.</p> <p>I'm running a large (to me) MIP using Gurobi in R on my local machine. (~2M binary decision variables, ~15K continuous decision variables).</p> <p>I have 256GB RAM and the model is only using about 40GB at max, during presolve, so that's not a bottleneck. My processor is puny though, only 4 cores and 4 threads. I'm awaiting delivery for a 18 core / 36 thread processor. Assuming I run the model on 35 of the 36 threads, on approximately what order of a speedup can I anticipate? I'm assuming there's a diminishing returns with more cores.</p> https://or.stackexchange.com/q/8542 3 Solution for a TSP with Branch and Cut for Gurobi in Java? Philip https://or.stackexchange.com/users/9817 2022-06-14T11:28:15Z 2022-06-15T02:37:41Z <p>We have a group project and our job is to create an algorithm for solving a TSP with Branch and Cut. (Use of lazy constraints.) We tried around but don´t know what is the best way to start. We get the first solution with the nearest neighbor heuristic. From there on we should start with the solution. We should use the Gurobi solver.</p> <p>What is the best way to get through this?</p> https://or.stackexchange.com/q/6638 1 CPLEX callback in pyomo Luca https://or.stackexchange.com/users/5964 2021-07-28T17:22:15Z 2022-06-18T15:44:02Z <p>I am trying to figure out what is the correct use of cplex callbacks in pyomo. In particular I am looking for the translation of the following example from gurobi to cplex:</p> <pre><code>from gurobipy import GRB import pyomo.environ as pe from pyomo.core.expr.taylor_series import taylor_series_expansion m = pe.ConcreteModel() m.x = pe.Var(bounds=(0, 4)) m.y = pe.Var(within=pe.Integers, bounds=(0, None)) m.obj = pe.Objective(expr=2*m.x + m.y) m.cons = pe.ConstraintList() # for the cutting planes def _add_cut(xval): # a function to generate the cut m.x.value = xval return m.cons.add(m.y &gt;= taylor_series_expansion((m.x - 2)**2)) _add_cut(0) # start with 2 cuts at the bounds of x _add_cut(4) # this is an arbitrary choice opt = pe.SolverFactory('gurobi_persistent') opt.set_instance(m) opt.set_gurobi_param('PreCrush', 1) opt.set_gurobi_param('LazyConstraints', 1) def my_callback(cb_m, cb_opt, cb_where): if cb_where == GRB.Callback.MIPSOL: cb_opt.cbGetSolution(vars=[m.x, m.y]) if m.y.value &lt; (m.x.value - 2)**2 - 1e-6: cb_opt.cbLazy(_add_cut(m.x.value)) opt.set_callback(my_callback) opt.solve() </code></pre> https://or.stackexchange.com/q/4740 13 How to handle an IP sub-problem with an objective function in Benders Decomposition whitepanda https://or.stackexchange.com/users/4025 2020-08-26T23:21:07Z 2022-06-18T09:35:39Z <p>I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) including only integer variables. In addition, suppose that the SP generated does not hold any nice property like total unimodularity meaning that the relaxation does not do any good for me. In this case, I cannot utilize the duality theorem to generate a Benders cut.</p> <p>I am familiar with Logic-Based BD (LBBD). Yet, in all the studies that I have seen using LBBD, SP becomes a feasibility problem without an objective function, which is solved by constraint programming (CP).</p> <p>Now, let's further assume that the SP has a solid objective function. I was wondering if there are recent studies containing LBBD where SP is an IP with an objective function and is not solved with CP. If not, what are some viable approaches to tackle such problem settings?</p> https://or.stackexchange.com/q/4581 2 How to display the range of coefficients in docplex log? EhsanK https://or.stackexchange.com/users/36 2020-07-24T15:20:58Z 2022-06-22T17:58:41Z <p>A typical gurobi log can have a section where it shows the range of coefficients. Something like:</p> <pre><code>Coefficient statistics: Matrix range [1e+00, 6e+01] Objective range [5e+01, 9e+01] Bounds range [1e+00, 1e+00] RHS range [2e+04, 2e+04] </code></pre> <p>I've been looking around the docplex package and so far, I've only found the <code>print_information</code> method of the <code>Model</code> class which only shows general statistics about the model such as number and type of variables and constraints.</p> <p>Is there a way to display the range of coefficients in docplex log?</p> <p>Note:</p> <ol> <li>CPLEX Interactive Optimizer has <code>display problem stats</code> but that's not what I'm looking for.</li> <li>I'm interested in knowing how or if this can be done in <a href="http://ibmdecisionoptimization.github.io/docplex-doc/" rel="nofollow noreferrer">docplex API</a> and not the <a href="https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/refpythoncplex/html/help.html" rel="nofollow noreferrer">cplex python API</a>.</li> </ol> https://or.stackexchange.com/q/375 19 Classics in Operations Research from around WW II? kjetil b halvorsen https://or.stackexchange.com/users/166 2019-06-11T16:41:46Z 2022-06-16T17:13:23Z <p>Once I found a site on the web containing some classic, original material from around the WW II. One of the topics covered was submarine hunting. But I cannot find that again now ... </p> <p>So the question is: Where can I find original documents, especially applied ones, from that period? Preferably web sites, but failing that, other options are good. Also of interest are references to particularly illuminating documents from that period. I found the paper <em>British Operational Research in World War II</em> by Joseph F. McCloskey, Operations Research, Vol. 35, No. 3 (May - Jun., 1987), pp. 453-470 (on JSTOR.) </p>