Recent Questions - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2020-11-25T11:52:09Z https://or.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/5278 1 Implement geometric constraint using DOCplex s6nke https://or.stackexchange.com/users/4484 2020-11-25T10:53:31Z 2020-11-25T10:53:31Z <p>currently I'm working on a wind farm layout optimization problem. I found an appropriate model in literature (Fischetti et al.) and now I'm trying to reproduce it using the Python API of cplex with DOCPlex. The model looks like the following:</p> <p><span class="math-container">\begin{align} \text{max} \ z = \sum_{i \in V} (P_i x_i - w_i) \end{align}</span></p> <p>s.t.</p> <p><span class="math-container">\begin{align} N_ {min} \le \sum_{i \in V} x_i \le N_{max} \\\\ x_i + x_j \le 1 \qquad (i,j) \in E_I \tag{eqn of interest}\\\\ \sum_{j \in V} I_{i,j} x_j \le w_i + M_i (1-x_i) \quad i \in V \\\\ w_i \in \{0,1\} \quad i \in V \\\\ w_i \ge 0 \quad i \in V \end{align}</span></p> <p>with the corresponding set <span class="math-container">$E_I$</span>: <span class="math-container">$\begin{equation} \{(i,j): i,j \in V, dist(i,j) &lt; D_{min}, i \neq j\} \end{equation}$</span></p> <p>From my understanding, this constraint ensures the mininum distance <span class="math-container">$D_{min}$</span> is achieved by comparing the current iterator <span class="math-container">$i$</span> with all already set locations <span class="math-container">$x_j$</span> in the distance of <span class="math-container">$D_{min}$</span>. If there would be a match, the eqn <span class="math-container">$x_i + x_j$</span> would be at least 2 (if the binary at <span class="math-container">$i$</span> would be set), violating the constraint. I am currently failing to add this constraint to my model in DOCcplex. If anyone could help my, by giving me a hint I would be glad.</p> <p>Thank you in advance</p> https://or.stackexchange.com/q/5277 2 Bioinformatics / Genomics Optimization Problems? Klumpi https://or.stackexchange.com/users/4478 2020-11-24T15:37:40Z 2020-11-25T11:27:23Z <p>I am a third year bioinformatics student and would like to apply my knowledge from an introductory course in Optimization Methods to some problems in the field of genomics or bioinformatics.</p> <p>Do you know any optimization problems in this context that a beginner in OR could solve?</p> https://or.stackexchange.com/q/5274 0 How to prove this convex-optimization problem? 이명훈 https://or.stackexchange.com/users/3983 2020-11-24T10:30:48Z 2020-11-24T10:49:06Z <p>I am struggling with the following optimization problems.</p> <p><strong>Problem 1</strong></p> <p><span class="math-container">\begin{align}\max_{\alpha, s_1, s_2}&amp;\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\text{s.t.}&amp;\quad s_1 \geq 0, s_2 \geq 0, \alpha \geq 0, \alpha \geq A-s_1 - \beta s_2\end{align}</span></p> <p><strong>Problem 2</strong></p> <p><span class="math-container">\begin{align}\max_{\alpha, s_1, s_2}&amp;\quad s_1 + s_2 - \gamma (s_1 (K_1 + s_1) + s_2 (K_2 + s_2) + \alpha K)\\\text{s.t.}&amp;\quad s_1 \geq 0, s_2 \geq 0, \alpha \geq 0, B-s_1 - \beta s_2 \leq \alpha \leq A-s_1 - \beta s_2\end{align}</span></p> <p>where <span class="math-container">$K_1 &gt;0, K_2 &gt;0, C&gt;0, 0&lt;\beta&lt;1, 0&lt;B&lt;A, \gamma &gt;0, c_1, c_2 &gt;0$</span> are constants.</p> <p>If for a given <span class="math-container">$\gamma = \gamma'$</span>, the optimal objective value of <strong>Problem 1</strong> is greater than that of <strong>Problem 2</strong>, is the optimal objective value of <strong>Problem 1</strong> greater than that of <strong>Problem 2</strong> for all <span class="math-container">$0&lt; \gamma &lt; \gamma'$</span>?</p> <p>I can prove this when the constraints <span class="math-container">$s_1, s_2, \alpha \geq 0$</span> do not exist. I proved it by determining a closed form solution for each problem and just compared the two (derivative with respect to <span class="math-container">$\gamma$</span> yields lower value for <strong>Problem 1</strong> for all <span class="math-container">$\gamma &gt;0$</span>). How can this be solved when the non-negativity constraints are introduced?</p> https://or.stackexchange.com/q/5273 -5 What type of algorithm corresponds to NP-HARD problems? [closed] fathese https://or.stackexchange.com/users/4273 2020-11-23T17:49:26Z 2020-11-23T17:49:26Z <p>If we have an NP-hard problem, is providing a formulation of polynomial-size a good contribution, and what is the exact definition of polynomial time</p> https://or.stackexchange.com/q/5271 2 How can I convexify (allowed some approximation) the objective function? dipak narayanan https://or.stackexchange.com/users/836 2020-11-23T12:31:13Z 2020-11-24T08:53:46Z <p>I have a known matrix, <span class="math-container">$H$</span> of size <span class="math-container">$U\times B$</span>. The optimization variable is <span class="math-container">$D$</span> of same size, which is binary</p> <p>Now I have <span class="math-container">$$S_u=\frac{\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}}{\sum\limits_{b=1}^{B}H_{u,b}-\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}},\quad \forall u\in\{1,\cdots, U\}$$</span> and I want to maximize <span class="math-container">$\sum\limits_{u=1}^US_u$</span>.</p> <p>UPDATE:</p> <p>with <span class="math-container">$bmin\le \sum_{b=1}^B D_{u,b}\le bmax, \forall u$</span> and</p> <p><span class="math-container">$\sum_{u=1}^{U}D_{u,b}\le umax, \forall b$</span></p> <p>Can I perform some alternative formulation so that the function becomes convex, or any convex approximation?</p> <p>EDIT:</p> <p>The denominator is strictly non-negative. The first or positive part of the denominator denotes the case where <span class="math-container">$D_{u,b}=1, \forall b, b=1,\cdots, B$</span></p> <p>Also, the elements in <span class="math-container">$H$</span> are non-negative.</p> <p>EDIT-2:</p> <p>what if I have</p> <p><span class="math-container">$$S_u=\frac{\sum\limits_{b=1}^{B} P_{u,b}D_{u,b}H_{u,b}}{\sum\limits_{u=1}^{U}\sum\limits_{b=1}^{B}P_{u,b}H_{u,b}-\sum\limits_{b=1}^{B} P_{u,b}D_{u,b}H_{u,b}},\quad \forall u\in\{1,\cdots, U\}$$</span> and I want to maximize <span class="math-container">$\sum\limits_{u=1}^US_u$</span>.</p> <p>where <span class="math-container">$0\le P_{u,b}\le P_{max,b}$</span> is also an optimization variable.</p> https://or.stackexchange.com/q/5269 1 How to describe the traveling salesman problem with an integer programming model? WindBreeze https://or.stackexchange.com/users/4077 2020-11-22T23:39:17Z 2020-11-23T13:50:41Z <p>I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal Hamilton circuit. We also always start at node 1. ex: 1 -&gt; 2 -&gt; 4 -&gt; 3 -&gt; 1 is a solution for a graph containing 4 nodes.</p> <p>I have the following constraints :</p> <p>(1) <span class="math-container">$\sum_{(i,j) \in A^+} y_{ij} = 1$</span> Here <span class="math-container">$y_{ij}$</span> is a binary variable. if it's equal to 1 it means that the edge <span class="math-container">$(i,j)$</span> is in the optimal path. <span class="math-container">$(i,j) \in A^+$</span> means all edges that enters in a node <span class="math-container">$A$</span>.</p> <p>(2) <span class="math-container">$\sum_{(j,i) \in A^-} y_{ji} = 1$</span> Same thing but with every edge that exits a node <span class="math-container">$A$</span>.</p> <p>In the following constraints we use <span class="math-container">$x_{ij} \geq 0$</span> which represents the flow on an edge <span class="math-container">$(i,j)$</span></p> <p>(3) <span class="math-container">$\sum_{(i,j) \in A^+(i)} x_{ij} = |V|$</span> when <span class="math-container">$i \in V \text{ , } i = 1$</span> This means that the total flow that exit through the various edges going out of node 1 is equal to the number of nodes in the graph.</p> <p>(4) <span class="math-container">$\sum_{(i,j) \in A^+(i)} x_{ij} - \sum_{(j,i) \in A^-(i)} x_{ji} = -1$</span> when <span class="math-container">$i \in V \text{ , } i \neq 1$</span> This means that a node i consume one unit of flow. The exception is node 1.</p> <p>(5) <span class="math-container">$\sum_{(j,i) \in A^-(i)} x_{ji} = 1$</span> when <span class="math-container">$i \in V \text{ , } i = 1$</span> This means that the flow that is sent to node 1 is equal to 1. This correspond to when we arrive to our destination ex: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 1.</p> <p>This programming model is not complete as long as I do not link the binary variables with the flow variables. However I don't understand how to do it properly. Should a new constraint be added?</p> https://or.stackexchange.com/q/5267 6 Is the solution of a convex combination of the objective in simple problems a convex combination of the solutions of the same problems? Patricio https://or.stackexchange.com/users/2391 2020-11-22T19:21:25Z 2020-11-24T14:56:01Z <p>Let <span class="math-container">$\mathbf{A}=\left(a_{ij}\right)$</span> be a <span class="math-container">$n\times J$</span> matrix with <span class="math-container">$a_{ij}\geq 0$</span>, <span class="math-container">$n&gt;J$</span> and such that no row has all its entries equal to zero, and each column has at most one zero. Let also <span class="math-container">$\mathbf{q}=\left(q_i\right)$</span> a <span class="math-container">$n\times 1$</span> vector of variables. Abusing notation, I'll write <span class="math-container">$\mathbf{q}^{\beta}=\left(q_i^{\beta}\right)$</span> for some <span class="math-container">$\beta&gt;1$</span>. Finally, let <span class="math-container">$\mathbf{w}=\left(w_j\right)_{1\leq j\leq J}$</span> with <span class="math-container">$w_{j}\geq 0$</span> and <span class="math-container">$\sum_{j=1}^{J}w_{j}=1$</span>.</p> <p>Consider the problem</p> <p><span class="math-container">\begin{align} \min\limits_{\{q_i\}}&amp; \quad \left(\mathbf{A}\mathbf{w}\right)^{\top}\mathbf{q}^{\beta}\\ \text{s.t.}&amp;\quad \quad \begin{cases} \sum_{i=1}^n q_i=1\\ \mathbf{q}\geq 0. \end{cases} \end{align}</span></p> <p>and, in particular, the specific problems that result from choosing <span class="math-container">$\mathbf{w}=\mathbf{e}_k=\left(e_j\right)_{1\leq j\leq J}$</span> with <span class="math-container">$e_{k}=1$</span> and <span class="math-container">$e_{j}=0\;\forall j\neq k$</span> for <span class="math-container">$k=\{1,\dots,J\}$</span>. Observe that the objetive function in the general problem above is a convex combination of the objective in the <span class="math-container">$J$</span> specific problems. Let <span class="math-container">$\mathbf{q}^k$</span> denote the minimand for each <span class="math-container">$\mathbf{e}_k$</span> and call <span class="math-container">$\mathbf{z}^k=\mathbf{A}^{\top}\left(\mathbf{q}^k\right)^{\beta}$</span>.</p> <p>If we call <span class="math-container">$\mathbf{\hat q}$</span> the solution to the general problem for <span class="math-container">$\mathbf{w}\neq\mathbf{e}_k\;\forall k$</span>, I believe that there exists <span class="math-container">$\mathbf{w}^{\prime}$</span> (with <span class="math-container">$w_j^\prime\geq 0$</span> and <span class="math-container">$\sum w_j^\prime&gt;0$</span>) such that <span class="math-container">$\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}=\sum_{k=1}^J\mathbf{z}^kw_k^\prime$</span>. In other words, the solution to the general problem is a convex combination of the solutions to the specific problems. Is this correct? If it is, can you provide a reference for the proof?</p> <p><strong>Edit:</strong></p> <p>Following @mtanneau's suggestion, I've obtained the closed form solution for the optimal <span class="math-container">$\mathbf{q}\left(\mathbf{w}\right)=\left(q_i\left(\mathbf{w}\right)\right)$</span> given <span class="math-container">$\mathbf{w}$</span>. To simplify notation, write <span class="math-container">$\mathbf{\bar a}\left(\mathbf{w}\right)=\left(\bar a_i\left(\mathbf{w}\right)\right)=\mathbf{Aw}$</span>, where <span class="math-container">$\bar a_i\left(\mathbf{w}\right)$</span> is just the weighted average of the values on row <span class="math-container">$i$</span> (with weights given by <span class="math-container">$\mathbf{w}$</span>). Two cases:</p> <ol> <li><p>Given <span class="math-container">$j$</span>, <span class="math-container">$\exists i^{*}\,|\,a_{i^{*}j}=0$</span>. The assumptions on <span class="math-container">$\mathbf{A}$</span> warrant that <span class="math-container">$i^*$</span> is unique, and that if <span class="math-container">$\mathbf{w}$</span> is such that <span class="math-container">$\bar a_{i^*}\left(\mathbf{w}\right)=0$</span>, it must be the case that <span class="math-container">$\bar a_{i}\left(\mathbf{w}\right)&gt;0\;\forall i\neq i^*$</span>. The solution to the specific problem is <span class="math-container">$q_{i^*}\left(\mathbf{e}_j\right)=1$</span> and <span class="math-container">$q_{i}\left(\mathbf{e}_j\right)=0\,\forall i\neq i^*$</span>, and, simmilarly, for those <span class="math-container">$\mathbf{w}$</span> such that <span class="math-container">$\bar a_{i^*}\left(\mathbf{w}\right)=0$</span>, that of the general problem is <span class="math-container">$q_{i^*}\left(\mathbf{w}\right)=1$</span> and <span class="math-container">$q_{i}\left(\mathbf{w}\right)=0\,\forall i\neq i^*$</span> (if <span class="math-container">$\bar a_{i}\left(\mathbf{w}\right)&gt;0\,\forall i$</span>, the solution follows the structure in (2) below).</p> </li> <li><p>Given <span class="math-container">$j$</span>, <span class="math-container">$a_{ij}&gt;0\;\forall i$</span></p> </li> </ol> <p><span class="math-container">$$q_i\left(\mathbf{w}\right)=\frac{1}{\bar a_i\left(\mathbf{w}\right)^{\beta-1}\sum_{i^{*}=1}^n\left(\frac{1}{\bar a_{i^{*}}\left(\mathbf{w}\right)}\right)^{\beta-1}}$$</span>.</p> <p>When <span class="math-container">$\mathbf{w}=\mathbf{e}_k$</span>, this simplifies to</p> <p><span class="math-container">$$q_i\left(\mathbf{e}_k\right)=\frac{1}{a_{ik}^{\beta-1}\sum_{i^{*}=1}^n\left(\frac{1}{a_{i^{*}k}}\right)^{\beta-1}}$$</span>.</p> <p>I don't see how to proceed from here.</p> https://or.stackexchange.com/q/5266 -4 difference between lower bounds and upper bounds for an optimization problem [closed] fathese https://or.stackexchange.com/users/4273 2020-11-22T17:42:10Z 2020-11-22T17:42:10Z <p>What is the exact definition of a lower and an upper bound for an optimization problem in general like routing and scheduling?<br/> What are the most known methods for generating tight lower bounds? and what is the relation between linear relaxation and lower bounds <br/> What are the most known methods for generating tight lower bounds? <br/> Why did we insist generally in the literature on the lower bounds methods rather than upper bounds?<br/></p> https://or.stackexchange.com/q/5262 5 Shortest path problem with underlying continuous variables Tobia Marcucci https://or.stackexchange.com/users/994 2020-11-21T19:29:16Z 2020-11-24T00:06:15Z <p>I recently got interested in the following variation of the shortest path problem. I've looked in the literature for days but I couldn't find any paper studying this problem. I'd like to ask if you have seen this problem (or any similar problem) before, and if you could point me to some relevant literature.</p> <p>In a few words, the problem is as follows. We have a directed graph <span class="math-container">$G = (V, E)$</span>. For each vertex <span class="math-container">$v \in V$</span> we have a set <span class="math-container">$S_v \in \mathbb R^m$</span> (say convex) and a point in it <span class="math-container">$x_v \in S_v$</span>. The length of the edge <span class="math-container">$(u,v) \in E$</span> is, e.g., the Euclidean distance between <span class="math-container">$x_u$</span> and <span class="math-container">$x_v$</span>. A path <span class="math-container">$P$</span> from source <span class="math-container">$s \in V$</span> to destination <span class="math-container">$d \in V$</span> is defined the usual way. The length of the path <span class="math-container">$P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$</span>, on the other hand, is defined as the minimum w.r.t. the point locations <span class="math-container">$x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$</span> of the sum of the lengths of the edges <span class="math-container">$(v_1, v_2), \ldots, (v_{n-1}, v_n)$</span>. Among all paths from <span class="math-container">$s$</span> to <span class="math-container">$d$</span>, we seek one of minimum length.</p> <p>This problem has the flavor of the &quot;Euclidean shortest path&quot; (see e.g. Sharir and Schorr, &quot;On Shortest Paths in Polyhedral Spaces&quot;) which is common in robot navigation, but it has important differences. I've also seen shortest path problems with generalized arc lengths (see e.g. Frieze, &quot;Minimum Paths in Directed Graphs&quot;), but this problem formulation doesn't quite match the one above either.</p> <p>Any thoughts/ideas?</p> https://or.stackexchange.com/q/5261 3 What are the flow based formulations? fathese https://or.stackexchange.com/users/4273 2020-11-21T18:19:01Z 2020-11-22T16:50:06Z <p>What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?</p> <p>Also, the same question for the time staged formulation.</p> https://or.stackexchange.com/q/5259 6 How to model bicycle sharing scheme? bajun65537 https://or.stackexchange.com/users/4465 2020-11-21T03:27:57Z 2020-11-22T18:46:59Z <p>One of the problems I have recently considered is the problem of rebalancing bicycle stations for bike-sharing schemes all over the world. It is not a secret that the demand for bikes across the city varies (some people, including myself, prefer to go downhill rather than uphill, other ride a bike only during sunny weather etc.). Thus, resulting in a serious disproportion of available bikes among different stations at different times of the day. As a result, bike-sharing companies hire men with a van to pick up bikes from less used locations to locations with high demand.</p> <p>How would one go about trying to model that? I am fairly familiar with the concept of networks in operations research. However, this seems to be far more complex. Would it be possible to create a list of stations (nodes) from which the driver would have to pick a certain amount of bikes and transport them elsewhere (to other station/ node)?</p> <p>Suppose that I have data on <code>starting station</code>, <code>ending station</code>, <code>duration of the ride</code>, <code>coordinates of each station</code>. From a more practical point of view - what might be the right place to get data on the distance between nodes? Assuming the straight lines between nodes seems like a quite of simplification, however, this is what I am trying to do, simplify and then solve the easier problem. If, however, this is an oversimplification, where to get real data on the distances? I tried google's static API but it does not work for me even after I signed up and everything.</p> https://or.stackexchange.com/q/5256 7 OR-TOOLS : delivery node with multiple possible pickup nodes Kuifje https://or.stackexchange.com/users/2556 2020-11-20T14:51:46Z 2020-11-20T15:04:43Z <p>I am using ortools to model a VRP with pickup and delivery constraints, where pickups can be done at different nodes. For example, if node A has a demand, it must be picked at node B or C.</p> <p>Here is how I do this:</p> <pre><code># data[&quot;pickups_deliveries&quot;] is a dict with keys delivery_nodes and values a list of possible pickup nodes # example : data[&quot;pickups_deliveries&quot;][a] = [b,c] for delivery_node in self.data[&quot;pickups_deliveries&quot;]: # choose one node among all pickup options all_pickups = [ self.manager.NodeToIndex(p) for p in self.data[&quot;pickups_deliveries&quot;][delivery_node] ] self.routing.AddDisjunction(all_pickups, 0) # same vehicle for pickup and delivery delivery_index = self.manager.NodeToIndex(delivery_node) self.routing.solver().Add( sum( self.routing.ActiveVar(p) * self.routing.VehicleVar(p) for p in all_pickups ) == self.routing.VehicleVar(delivery_index) ) # precedence constraint time_dimension = self.routing.GetDimensionOrDie(&quot;Time&quot;) self.routing.solver().Add( sum( self.routing.ActiveVar(p) * time_dimension.CumulVar(p) for p in all_pickups ) &lt;= time_dimension.CumulVar(delivery_index) ) </code></pre> <p>This works if everything fits into 1 vehicle. But if capacity constraints require more than 1 vehicle, the solver does not find a solution after a few minutes (solver status 3).</p> <p>I suspect something is wrong with the constraints imposing that the same vehicle is used for the pickup and delivery, but I am not sure. I have also tried using the following code (from<a href="https://github.com/google/or-tools/issues/968" rel="noreferrer"> here</a>), but it does not help:</p> <pre><code>pickup_vehicles = [self.routing.VehicleVar(i) for i in all_pickups] deliver_vehicle = [self.routing.VehicleVar(delivery_index)] self.routing.solver().AddConstraint( self.routing.solver().Max(pickup_vehicles)== self.routing.solver().Max(deliver_vehicle)) </code></pre> <p>Can someone help ? Thanks!</p> <p><em>Note : I have cross posted on ortools <a href="https://groups.google.com/g/or-tools-discuss" rel="noreferrer">mailing list</a>.</em></p> https://or.stackexchange.com/q/5254 5 Counting the number of matchings in a complete bipartite graph Djames https://or.stackexchange.com/users/609 2020-11-20T14:15:31Z 2020-11-21T16:44:07Z <p>I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is <span class="math-container">$n!$</span> <em>perfect</em> matchings in the graph <span class="math-container">$\mathcal{K}_{n,n}$</span>. However, I cannot seem to figure out how many matchings this graph contains. I have experimented a bit, and the number seems to be very large. I have repeatedly solved the IP <span class="math-container">\begin{align} \min &amp;\ \sum_{i=1}^n\sum_{j=1}^n x_{ij }\\ \mbox{s.t.:}\ &amp; \sum_{i =1}^n x_{ij}=1,&amp;&amp;\forall j=1,\dots,n\\ \ &amp; x_{ij}\in\{0,1\},&amp;&amp;\forall i,j=1,\dots,n \end{align}</span> and then added no-good'' inequalities to remove the current solution until the solver (CPLEX) declared the problem infeasible. For <span class="math-container">$n=1,2,3,4$</span> I have gotten the numbers <span class="math-container">$1,4,27,256$</span> which suggests that the number of matchings should be <span class="math-container">$n^n$</span>. But <span class="math-container">$n=5$</span> gave me <span class="math-container">$3174$</span> matchings (not the expected <span class="math-container">$5^5=3125$</span>).</p> <p>Can anyone guide me to the number of mathings in <span class="math-container">$\mathcal{K}_{n,n}$</span>?</p> <hr /> <p>Edit: The no-good inequalities I use are the following <span class="math-container">\begin{equation} \sum_{(i,j):\bar{x}_{ij}=1}x_{ij}\leq n-1 \end{equation}</span> where <span class="math-container">$\bar{x}$</span> is the solution I want to cut out.</p> <p>It turns out that @Kuifje was right and that I had a bug in my code. After fixing that, I get that there is <span class="math-container">$n^n$</span> solutions to my IP.</p> https://or.stackexchange.com/q/5253 3 R ompr MILPModel array multiplication? Ralph Asher https://or.stackexchange.com/users/3958 2020-11-20T14:09:19Z 2020-11-20T14:09:19Z <p>In R, I regularly ompr::MILPModel for optimization. I adapt the below snippet to enable multiplication of a decision variable with two dimensions (e.g., <code>x[i,j]</code> ) by a numeric matrix of the same dimensions, in constraints and the objective function. I chanced upon this code elsewhere, so I am not going to claim I much know what is going on <code>matrix_multiplication_fcn</code>, just that it works.</p> <p>I would like to be able to use MILPModel with decision variables of 3+ dimensions, e.g., <code>x[i,j,k]</code> or <code>x[i,j,k,m]</code> , and be able to multiply these decision variables against numeric arrays of the same dimension. I am having a really hard time figuring out how to make an <code>array_multiplication_fcn</code> of 3+ dimensions that has the same effect.</p> <p>I've made a couple attempts but when I look at the model's objective function, it's just the first two or three values from the numeric array, repeated over and over.</p> <pre><code>mat1 &lt;- matrix(ncol=10,nrow=4,runif(400)) #define this function, it will be necessary for matrix multiplication inside a MILPModel matrix_multiplication_fcn &lt;- function(static_matrix, row_variable, column_variable){ vapply(seq_along(row_variable), function(k) static_matrix[row_variable[k], column_variable[k]], numeric(1L)) } milp_model &lt;- ompr::MILPModel() %&gt;% add_variable(assign_units[rowindex,colindex], rowindex=1:4,colindex=1:10,type='binary') %&gt;% #total binaries ==10 add_constraint(sum_expr( assign_units[rowindex,colindex],rowindex=1:4,colindex=1:10 )==10 ) %&gt;% #sum of binaries * mat1 &lt;= 7 add_constraint( sum_expr( ompr::colwise( matrix_multiplication_fcn(static_matrix=mat1,row_variable=rowindex,column_variable=colindex)) * assign_units[rowindex,colindex], rowindex = 1:4, colindex = 1:10) &lt;= 7) %&gt;% #objective: maximize value set_objective(sum_expr( ompr::colwise(matrix_multiplication_fcn(static_matrix=mat1,row_variable=rowindex,column_variable=colindex)) * assign_units[rowindex,colindex], rowindex=1:4,colindex= 1:10),sense='max') milp_model_out &lt;- milp_model %&gt;% ompr::solve_model(with_ROI(solver = &quot;glpk&quot;,verbosity=-2,gap_limit=0,time_limit=180, node_limit=-1,first_feasible=FALSE))<span class="math-container">`</span> </code></pre> https://or.stackexchange.com/q/5252 1 Get array of sequences for array of interval arrays in OPL Adam Bajger https://or.stackexchange.com/users/4459 2020-11-19T22:20:24Z 2020-11-21T10:04:10Z <p>So I want to define multiple sequences (an array of them). I have this:</p> <pre><code>dvar interval casy[d in 1..Domy][ukol in Ukoly] size Trvani[ukol]; dvar sequence S[d in 1..Domy] in i in casy[d]; </code></pre> <p>I get an error: <code>Cannot use domain type dvar interval[][Ukoly] for dvar sequence</code>. But when I use:</p> <pre><code>dvar interval casy[ukol in Ukoly] size Trvani[ukol]; dvar sequence S in i in casy; </code></pre> <p>everything just runs fine. Also, when I use</p> <pre><code>dvar interval casy[d in 1..Domy][ukol in Ukoly] size Trvani[ukol]; dvar sequence S[d in 1..Domy] in i in casy; </code></pre> <p>it works, but the sequences are for all the intervals, which I dont want. I want to have different sequences separately for each array of intervals, indexed by <code>d</code>.</p> <p>I just can't understand why would it use the array of intervals when I declare it normally, but would complain when I pull the same exact interval from an array by its index.</p> <p>Is there something I am missing?</p> https://or.stackexchange.com/q/5250 1 How to model this problem that contains two linked uncertainties? SAH https://or.stackexchange.com/users/3500 2020-11-19T11:06:41Z 2020-11-21T15:43:45Z <p>A milk factory has to sign a weekly contract with consumer A and B, in advance, in order to sell its product. Consumer A, wants the average delivered milk during each week be equal to the contracted volume, otherwise the factory has to pay a penalty for scarcity. On the other hand, Consumer B wants the daily delivered volume to be equal to contracted volume, otherwise has to pay a penalty for daily scarcity. Practically, A cares about weekly uncertainty and B cares about daily uncertainty. However, it is evident that the two uncertainty are correlated.</p> <p><span class="math-container">$c_A$</span> /<span class="math-container">$c_B$</span> are positive prices for promising to sell <span class="math-container">$X_A$</span>/<span class="math-container">$X_B$</span> milk to consumer A / B. <span class="math-container">$c_a$</span> and <span class="math-container">$c_b$</span> are negative prices for scarcity of the product in market A and B during the contracted period.<span class="math-container">$x_A$</span> / <span class="math-container">$x_B$</span> is the delivered milk in real time period. <span class="math-container">${x_A}^{-}$</span> and <span class="math-container">${x_B}^{-}$</span> measures the real-time scarcity of the promised delivery. <span class="math-container">$X_{max}$</span> is the capacity of milk company. The available daily and also weekly milk is uncertain and follow distribution <span class="math-container">$\delta$</span> and <span class="math-container">$\omega$</span>.</p> <p>given that the aim is to maximize the revenue, here is what I have done so far:</p> <p><span class="math-container">$c_AX_A + c_BX_B + \mathbb{E_{\omega}}[{c_a x_A}^{-}]+\mathbb{E_{\delta}}[{c_b x_B}^{-}] \\ X_A + X_B \leq X_{max} \\ X_A - x_A \geq {x_A}^{-} \\ X_B - x_B \geq {x_B}^{-}\\ X_A, X_B, x_A, x_B, {x_B}^{-}, {x_A}^{-} \geq 0 \\$</span></p> <p>How can I link the uncertain product to the allocated ones to each consumer with a constraint.</p> <p>How many stages does this stochastic program contain?</p> <p>Given that we have historical daily milk product, how can one form the two distribution?</p> <p>How does the scenario tree look like?</p> https://or.stackexchange.com/q/5249 3 What is the difference between min- cut formulation and (bi) partitioning formulation? fathese https://or.stackexchange.com/users/4273 2020-11-19T10:01:58Z 2020-11-19T14:57:43Z <p>I have a min-cut formulation and a bi-partitioning problem. The two problems focus on finding the minimal cut value separating the two partitions? So what are really the differences between the problems? what are mainly the considered objectives and constraints?</p> https://or.stackexchange.com/q/5248 1 MILP formualtion for Two-level minimum dominating set (MDS) problem? Amedeo https://or.stackexchange.com/users/4347 2020-11-19T01:49:04Z 2020-11-19T01:49:04Z <p>I'm working on an optimization problem which is kind of finding the minimum dominating set (MDS) or the minimum vertex set (MVS) in an undirected graph. given the MILP formulation for both problems, <strong>I was wondering is there a way to state a constraint to find the (minimum) of (the minimum set)</strong>. In other words, given the set <strong>C</strong> is the solution of MDS with some edges, I am looking for a constraint that relates this set <strong>C</strong> using a new decision variable/s to find a new set <strong>P</strong> which is the MDS of the set <strong>C</strong>. <strong>The problem is like finding the root (or multiple roots) of an undirected graph in two linked stages</strong>. I can imagine that the problem will go like this, given:</p> <pre><code> x_v is the decision variable for the node to be selected in C (first level or child) y_v is the decision variable for the node to be selected in P (second level or parent (root)) z(u,v) is the decision variable about the edges of the graph resulting from solving the first level </code></pre> <p>hence, the constraint that relates those variables are:</p> <pre><code> y_v &lt;- x_v # to ensure that the parent node will be selected from the set of child nodes y_v &lt;- z(u,v) # to ensure that the parent node will be selected from the resulting edges </code></pre> <p>I can not figure out another constraint that forces the solver to select the set from the resulting set. As an example, consider the set <strong>C</strong> is <strong>{1,2,5,7}</strong>, Is there a way to promote node <strong>7</strong> as a root if I have the edges <strong>[(7,5),(7,2),(7,1)]</strong>. Please be noted that I meant by the root here is the node that at least connected to each child with one link.</p> <p>Any guidance will be very appreciated?</p> https://or.stackexchange.com/q/5245 2 Reading MPS file for linear programming and reconstructing the Optimization model S_Scouse https://or.stackexchange.com/users/2546 2020-11-18T22:00:41Z 2020-11-18T23:47:09Z <p>Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and solve using lpsolve. But I would like to run a sensitivity test by modifying the RHS of a certain constraint. Therefore, it would be helpful if I could reconstruct the constraints from the MPS file.</p> https://or.stackexchange.com/q/5244 2 Production planning for a video game economy beta0x64 https://or.stackexchange.com/users/4445 2020-11-18T18:40:53Z 2020-11-19T01:25:03Z <p>I'm a software developer who likes to play a video game that has a complex economy. I realized that the type of problem I'm trying to solve mimics real life operations research problems, and I am seeking your assistance in designing an OR-Tools model that would solve a scheduling problem given several constraints. I'm new to OR-Tools and finding some difficulties with describing my problem in the form of constraint programming. I already have python code that can unravel the requirements into phases of production naively based off of the total raw materials required for each component.</p> <p>I've answered the following questions:</p> <p><strong>What is the known information in this problem?</strong></p> <p>There are five planets with mining and production machines.</p> <p>It takes roughly 3 minutes to travel from planet to planet.</p> <p>Each mining machine can do 2 jobs, each production machine can do 5 jobs.</p> <p>The maximum amount each job can do is 100 units.</p> <p>Mining machines are used to extract raw resources. Production machines are used to make 1. components to producible items 2. producible items themselves. Sometimes producible items also require a combination of raw materials and producible items.</p> <p>It takes about 1 minute to travel between mining and production terminals on the same planet.</p> <p>These five planets have overlapping but different sets of resources on each.</p> <p>For example, Planet A has &quot;chemicals&quot;, &quot;biomass&quot;, &quot;copper&quot; and Planet B has &quot;carbon&quot;, &quot;chemicals&quot;, &quot;biomass&quot;.</p> <p>There are many, many items. Here is an example: A first aid kit requires 1 bioplasma and 1 textiles. A unit of bioplasma takes 3 biomass. A textile requires 2 biomass (not bioplasma) and 1 refined chemical. 1 refined chemical takes 3 chemicals. We will want to combine different orders that will share raw materials and intermediate items.</p> <p>In order to mine 100 raw materials, it generally takes about 23 minutes. It takes about 14 seconds to mine one raw material. In order to produce items, it varies depending on the number of raw materials that go into each item. This isn't public information but can be reverse engineered. I can determine this formula later as needed.</p> <p>We do know what each producible item requires and all the raw materials and their locations. This has been entered into a large spreadsheet built as an adjacency matrix.</p> <p>Technically, each planet has a player's storage with a capacity that can be expanded for money, transferring items between planets costs money, and traveling between planets also costs money. Profitability isn't really a concern however, because it's a given that fulfilling the order will be profitable. Our real goal is to have a fast turnaround time.</p> <p><strong>What are the decision variables or unknowns in this problem?</strong></p> <p>We don't know how much of each producible item an order will request until the request is made. We don't know what combination of producible items will be requested until the request is made. Which jobs should occupy each slot? How much of each item in the job should we do? What order should we do these operations?</p> <p><strong>What are the constraints on these variables?</strong></p> <p>Each planet has a set of mining machines and production machines. Each mining machine can only do 2 jobs. Each production machine (including intermediate items) can do 5 jobs at once. It takes 3 minutes to transition between planets. It takes about 1 minute to travel between mining and production terminals on the same planet. You can't collect output of the jobs early. They must complete and can't be interrupted once started.</p> <p><strong>What is the objective?</strong></p> <p>The objective is to produce a schedule of mining/production operations that minimizes our time spent in the game. Essentially, a production plan and schedule.</p> <p><strong>What am I asking you for?</strong></p> <p>I'd like your sagely advice on how to describe this problem in the form of constraint programming/scheduling/production planning. The output would be a list of operations needed to fulfill an order of products.</p> <p><strong>Some Examples</strong></p> <p>Let's say we wanted to fulfill an order of 100 first aid kits.</p> <p>This would require 100 bioplasma and 100 textiles.</p> <p>100 bioplasma would require 300 biomass.</p> <p>100 textiles would require 200 biomass and 100 refined chemicals.</p> <p>100 refined chemicals would require 300 chemicals.</p> <p>In total, 500 biomass and 300 chemicals are required in raw materials.</p> <p>A naive answer might look like:</p> <ol> <li><p>Go to Planet A and start 2 jobs of mining biomass, for a total of 200.</p> </li> <li><p>Then go to Planet B and start 2 jobs of mining 100 chemicals. 23 minutes elapse, and the player would mine 100 more chemicals and 100 more biomass on Planet B.</p> </li> <li><p>Go back to Planet A and start another 2 jobs of mining 100 biomass each.</p> </li> <li><p>After transferring all the raw materials back to one of the Planets, let's say Planet A, the player could then start 3 jobs of refining ~33 bioplasma (consuming 300 biomass) and then start 2 jobs of refining 50 refined chemicals (consuming 300 chemicals).</p> </li> <li><p>After about 34 minutes elapse, they start 5 jobs of refining 20 textiles, taking about 23 minutes.</p> </li> <li><p>Finally, they start 5 jobs of producing 20 first aid kits each, for a total of 100 first aid kits. As you can see, the jobs can be split up across the &quot;slots&quot; to speed up the process.</p> </li> </ol> https://or.stackexchange.com/q/5238 2 Maximum bipartite matching with breakpoints in edge weight function Anisotropic https://or.stackexchange.com/users/4442 2020-11-18T06:16:26Z 2020-11-19T14:21:15Z <p>I am looking for an analogy to the problem I am facing or better yet a paper or even code.</p> <p>I have:</p> <p>Nodes from set A and B.</p> <p>Edges are from a single A to many B.</p> <p>I am framing a max bipartite matching problem where the edge weights change at thresholds. If I have 9 edges between a single node in A and 9 nodes of B, and then a new edge is incorporated into that node A, all of its edge weights should be discounted by a factor.</p> <p>I am having some trouble with finding relevant literature about this problem.</p> <p>My objective function is a shopper wanting to purchase as many things that they can to make them <code>happy</code> while minimizing the <code>cost</code> of the order. Happiness can be a function of the full set of items. Some customers might be happier with a diverse set of products, some just want one thing.</p> <p>They make a purchase where prices change depending on the composition of the items ordered. In my case there is a <code>discount</code> given for buying more than a number of items in a certain <code>category</code>.</p> <p>A shopper has a utility for any given item and the store is offering discounts for certain families of items. e.g. buy 5 chocolate bars and get a dollar off.</p> <p>So I can buy 4 Hershey's bars and it's $5.</p> <p>But if I buy 4 Hershey's bars and a snickers (extra 80 cents), I can get the whole set of candy bars for$1 off and be better off in terms of me being more happy and paying less.</p> <h2>Limits:</h2> <p>There are &lt;100 A nodes. (Shopper)</p> <p>There are &lt; 10,000 B nodes (Items)</p> <p>There should be a max of 3 discount factors for 3 categories of items (total of 9). e.g. -</p> <ul> <li><p>More than 5 candy bars --&gt; Get 1 free</p> </li> <li><p>More than 50 candy bars --&gt; Get 5 free</p> </li> <li><p>More than 100 candy bars --&gt; Get some other item for free</p> </li> <li><p>More than 2 cases of soda --&gt; get one free</p> </li> <li><p>More than 10 cases of soda --&gt; get 4 free</p> </li> <li><p>More than 20 cases of soda --&gt; get 6 free</p> </li> </ul> <p>Any node will have a maximum degree of ~1000.</p> https://or.stackexchange.com/q/5233 6 OR-TOOLS : is it possible to partially fulfill a demand? Kuifje https://or.stackexchange.com/users/2556 2020-11-17T15:07:32Z 2020-11-20T15:32:09Z <p>I am working on a vehicle routing problem with <a href="https://developers.google.com/optimization/routing" rel="noreferrer">or-tools</a>.</p> <p>Is it possible to partially fulfill a demand? I know it is possible to <a href="https://developers.google.com/optimization/routing/penalties" rel="noreferrer">drop nodes</a> with the disjunction constraints. But in this case, a node is either visited, or not. I would like to allow a node to be visited, with the possibility to deliver only a fraction of its demand, if it is profitable. For example, for a given customer with demand <span class="math-container">$2$</span>, there might not be enough resources (vehicles/capacity) to complete its delivery, but there may be enough to deliver <span class="math-container">$1$</span> unit, and in this case the customer would be more happy than without any visit at all.</p> <p>Another way of saying this is that I would like to maximize the quantity that is delivered, while minimizing transportation costs.</p> <p>One option would be to duplicate nodes, each node having a given fraction of the demand. But this will quickly lead to very big networks and I don't think it is a good idea. Also, determining the values of the fractions may not be simple. The ideal fraction would be &quot;whatever spare space there is in the truck,&quot; but this is not straighforward to compute before hand.</p> <p>Is this possible with or-tools ?</p> https://or.stackexchange.com/q/5220 4 How to solve this convex problem heuristically? dipak narayanan https://or.stackexchange.com/users/836 2020-11-14T14:47:21Z 2020-11-18T22:43:33Z <p>I have the following problem</p> <p><span class="math-container">$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$</span> <span class="math-container">$$\text{subject to}$$</span> <span class="math-container">$$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$</span> <span class="math-container">$$\sum_{i=1}^{N_U}X_{i,j}\le b_{\max}, \forall j$$</span></p> <p>It is a convex problem,b ut I need a heuristic approach to solve this.</p> <p>Here, <span class="math-container">$R$</span> is a knowm matrix. <span class="math-container">$X$</span> is a binary matrix. <span class="math-container">$a_{\min}$</span>, <span class="math-container">$a_{\max}$</span> and <span class="math-container">$b_{\max}$</span> are also know. and positive</p> <p>Any suggestions</p> https://or.stackexchange.com/q/5183 2 PAVA-like solution to simple QP cfp https://or.stackexchange.com/users/3830 2020-11-09T14:02:49Z 2020-11-24T13:21:11Z <p>Let <span class="math-container">$l,u\in\mathbb{R}^n$</span>, and consider the QP:</p> <p><span class="math-container">$$\min_{l\le x\le u} {(\Delta x)^\top (\Delta x)}$$</span></p> <p>where <span class="math-container">$\Delta x=[x_2-x_1,\,x_3-x_2,\,\dots,\,x_n-x_{n-1}]^\top$</span>.</p> <p>I.e. we want to minimize the squared change in the elements of <span class="math-container">$x$</span> subject to <span class="math-container">$x$</span> being above the lower bound <span class="math-container">$l$</span> and below the upper bound <span class="math-container">$u$</span>.</p> <p>My hunch is that this is simple enough that it ought to have an exact &quot;pooled adjacent violators algorithm (PAVA)&quot; style solution. Is this correct? Has this problem been studied in the prior literature?</p> <hr /> <p>Aside: Of course as stated here the problem may have multiple solutions. I do not care which is returned.</p> <hr /> <p>Further aside: Here's MATLAB type code for an inefficient solution procedure. I expect there's a much more efficient algorithm!</p> <pre class="lang-matlab prettyprint-override"><code>while true xo = x; x( 1 ) = max( l( 1 ), min( u( 1 ), x( 2 ) ) ); for i = 2 : ( n - 1 ) x( i ) = max( l( i ), min( u( i ), 0.5 * ( x( i - 1 ) + x( i + 1 ) ) ) ); end x( n ) = max( l( n ), min( u( n ), x( n - 1 ) ) ); if all( abs( x - xo ) &lt; 1e-12 ) break end end </code></pre> https://or.stackexchange.com/q/5147 0 Is optimal solution to dual not unique if optimal solution to the primal is degenerate? BCLC https://or.stackexchange.com/users/3791 2020-11-04T08:07:41Z 2020-11-21T08:54:30Z <p>If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption?</p> <p>Spin-off from <a href="https://math.stackexchange.com/questions/1049796/prove-optimal-solution-to-dual-is-not-unique-if-optimal-solution-to-the-primal-i">here</a>.</p> <p>In my Operations Research problem set, our professor required us to prove</p> <blockquote> <p>&quot;If an optimal solution to the primal is degenerate, then there is at least one alternative optimal solution to the dual.&quot;</p> </blockquote> <p>I found, however, that if we do not assume uniqueness, the statement is <a href="https://math.stackexchange.com/questions/8393/primal-degenerate-optimal-dual-unique-optimal/8399#8399">false</a>?</p> <p>I asked by e-mail:</p> <blockquote> <p>&quot;In the problem set, does the optimal solution to the primal really need not be unique?&quot;</p> </blockquote> <p>The reply I got:</p> <blockquote> <p>&quot;Yes. Some LP problems have alternative optimal solutions.&quot;</p> </blockquote> <p>I asked if uniqueness was not needed to conclude an alternative optimal solution to dual and showed the counterexample I linked above (<a href="https://math.stackexchange.com/questions/8393/primal-degenerate-optimal-dual-unique-optimal/8399#8399">again here</a>).</p> <p>Reply I got:</p> <blockquote> <p>&quot;I only said thet in LP, alternative optimal solutions may exist. I am not referring to the problem in the exercise specifically. Please read the statement of the problem again.&quot;</p> </blockquote> <p>I then asked if the OP was equivalent to</p> <blockquote> <p>If there are several optimal solutions to the primal with at least one of them being degenerate or there is a unique degenerate optimal solution to the primal, then the optimal solution to the dual is not unique?</p> </blockquote> <p>i.e. (well so I think) uniqueness of degenerate optimal solution to primal is irrelevant.</p> <p>The reply I got:</p> <blockquote> <p>&quot;There is an additional assumption in your statement which is not in the problem.&quot;</p> </blockquote> <h2><strong>What is the additional assumption?</strong></h2> <p>In the end, we just copied the &quot;proof&quot; of one of our other classmates. Apparently, e was able to prove the statement even though it looks to be false. I don't have the proof with me though.</p> <p>One of my classmates asked our professor on the day of submission that someone (me) pointed out that if we don't assume uniqueness, the statement doesn't hold. I was kind of sleepy, but iirc, our prof said something that began with</p> <blockquote> <p>&quot;But that's not what you're trying to show&quot;</p> </blockquote> <p>or something like that. My classmate didn't respond, and we just moved on. Well, they did.</p> https://or.stackexchange.com/q/5106 5 How to determine if this problem is NP-HARD or NP-COMPLETE? fathese https://or.stackexchange.com/users/4273 2020-10-26T08:37:48Z 2020-11-24T10:56:26Z <p>Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes (for the N nodes) that minimizes the overall cut weights between the two pools.</p> <p>Is this considered a scheduling problem? If so what kind of scheduling problem?</p> <p>Is it NP-complete or NP-hard?</p> <p>Here is a pictorial explanation of the problem:</p> <p><a href="https://i.stack.imgur.com/EGtit.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/EGtit.png" alt="enter image description here" /></a></p> https://or.stackexchange.com/q/5077 4 Substituting inequality by equality constraints Patricio https://or.stackexchange.com/users/2391 2020-10-22T09:54:02Z 2020-11-21T19:44:41Z <p>Let <span class="math-container">$\mathbf{A}=\left(a_{ij}\right)$</span> be a <span class="math-container">$n\times J$</span> matrix with <span class="math-container">$a_{ij}\geq 0$</span>, <span class="math-container">$n&gt;J$</span> and such that no row or column has all its entries equal to zero. Let also <span class="math-container">$\mathbf{k}=\left(k_j\right)$</span> be a <span class="math-container">$J\times 1$</span> vector of non negative coeficients and <span class="math-container">$\mathbf{q}=\left(q_i\right)$</span> a <span class="math-container">$n\times 1$</span> vector of variables. Abusing notation, I'll write <span class="math-container">$\mathbf{q}^{\beta}=\left(q_i^{\beta}\right)$</span> for some <span class="math-container">$\beta&gt;1$</span>.</p> <p>For each <span class="math-container">$j$</span>, the following problem can be solved</p> <p><span class="math-container">\begin{align} \min\limits_{\{q_i\}}&amp; \quad \sum_{i=1}^n q_i^{\beta}a_{ij}\\ \text{s.t.}&amp;\quad \quad \begin{cases} \sum_{i=1}^n q_i=1\\ \mathbf{q}\geq 0. \end{cases} \end{align}</span></p> <p>Let <span class="math-container">$\mathbf{q}^j$</span> denote the minimand, <span class="math-container">$\mathbf{z}^j=\mathbf{A}^{\top}\left(\mathbf{q}^j\right)^{\beta}$</span>, <span class="math-container">$\mathbf{Z}=\left(z^j_j\right)$</span> the matrix resulting from adjoining all the <span class="math-container">$\mathbf{z}^j$</span> and <span class="math-container">$\langle \mathbf{Z}\rangle$</span> the convex cone spanned by <span class="math-container">$\mathbf{Z}$</span>. It can be shown that <span class="math-container">$\langle \mathbf{Z}\rangle\subseteq \langle \mathbf{A}\rangle$</span>. I'd like to prove that for <span class="math-container">$\mathbf{k}\in\langle \mathbf{Z}\rangle$</span>, problems</p> <p><span class="math-container">\begin{align} \max\limits_{\{q_i\}}&amp; \quad \sum_{i=1}^n q_i&amp;\quad &amp;\quad &amp;\quad &amp;\max\limits_{\{q_i\}}&amp;\sum_{i=1}^n q_i\\ \text{s.t.}&amp; \begin{cases} \mathbf{A}^{\top}\mathbf{q}^\beta\leq\mathbf{k}\\ \mathbf{q}\geq 0 \end{cases}&amp;\quad&amp;\quad &amp;\quad &amp;\text{s.t.}&amp; \begin{cases} \mathbf{A}^{\top}\mathbf{q}^\beta=\mathbf{k}\\ \mathbf{q}\geq 0 \end{cases} \end{align}</span></p> <p>yield the same result, i.e., all the inequality constraints other than the non negativity constraints are binding. I believe this result to be true also for <span class="math-container">$\beta=1$</span>.</p> <p><strong>Edit:</strong></p> <p>I'm trying to prove this by contradiction. Assume that the minimands are different and denote <span class="math-container">$\mathbf{\hat q}$</span> and <span class="math-container">$\mathbf{\tilde q}$</span> the solution to the problem with inequality and with equality constraints respectively. If <span class="math-container">$\mathbf{\hat q}\neq\mathbf{\tilde q}$</span>, then it must happen that</p> <ol> <li><span class="math-container">$\hat q=\sum_{i=1}^n \hat q_i&gt;\sum_{i=1}^n \tilde q_i=\tilde q$</span></li> <li><span class="math-container">$\mathbf{k}^{\prime}=\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}\leq\mathbf{k}$</span>, with strict inequality for some <span class="math-container">$j$</span></li> </ol> <p>I think that it suffices to show that <span class="math-container">$\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$</span>. Note that for <span class="math-container">$\mathbf{k}^{\prime}$</span>, both problems need to yield <span class="math-container">$\mathbf{\hat q}$</span> as the solution and, therefore, the assumption that <span class="math-container">$\mathbf{k}\in\langle \mathbf{Z}\rangle\implies \mathbf{\hat q}\neq\mathbf{\tilde q}$</span> cannot be true.</p> <p>I know that <span class="math-container">$k_j\geq k^{\prime}_j\geq \hat q^{\beta} z_j^j\;\forall j$</span>, but an example has convinced me that this is not enough to warrant <span class="math-container">$\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$</span> when <span class="math-container">$J&gt;2$</span> (it is enough for <span class="math-container">$J=2$</span>, though).</p> <p>I believe that some &quot;continuity&quot; argument must imply that, given <span class="math-container">$\mathbf{k}\in\langle \mathbf{Z}\rangle$</span>, there must exist some <span class="math-container">$\mathbf{k}^{\prime\prime}\in\langle \mathbf{Z}\rangle$</span> such that <span class="math-container">$\mathbf{k}^{\prime\prime}\leq\mathbf{k}$</span> and that the solution to the problem with inequality constraints is unchanged. On the other hand, the solution to the problem with equality constraints would be <span class="math-container">$\mathbf{\tilde q}^{\prime\prime}$</span> and <span class="math-container">$\sum_{i=1}^{n}=\tilde q^{\prime\prime}_i&gt;\tilde q$</span>. Could iterating this procedure yield <span class="math-container">$\tilde q \rightarrow \hat q$</span>?</p> <p><strong>Edit 2:</strong> Two other approaches, both of them incomplete:</p> <ol> <li><p>An alternative is trying to prove the contrapositive, i.e., <span class="math-container">\begin{equation*} \hat{\mathbf{q}}\neq\tilde{\mathbf{q}}\implies\mathbf{k}\not\in\langle \mathbf{Z}\rangle. \end{equation*}</span></p> <p>There are two cases:</p> </li> </ol> <ul> <li><span class="math-container">$\nexists \tilde{\mathbf{q}}$</span>. This can only happen if the feasible set is empty (if it is not empty, it is compact and convex, and since the objective function is continuous, it will reach a maximum). Let <span class="math-container">$\mathbf{w}=\left(w_{i}\right)_{1\leq i\leq n}$</span> with <span class="math-container">$w_{i}=q_{i}^{\beta}\geq 0$</span>. The feasible set being empty implies that <span class="math-container">$\nexists \mathbf{q}\geq 0$</span> such that <span class="math-container">$\mathbf{A}^{\top}\mathbf{q}^{\beta}=\mathbf{k}$</span> and, therefore, <span class="math-container">$\nexists \mathbf{w}\geq 0$</span> such that <span class="math-container">$\mathbf{A}^{\top}\mathbf{w}=\mathbf{k}$</span>. This means <span class="math-container">$\mathbf{k}\not\in\langle \mathbf{A}\rangle$</span> and, hence, <span class="math-container">$\mathbf{k}\not\in\langle \mathbf{Z}\rangle$</span>.</li> <li><span class="math-container">$\exists \tilde{\mathbf{q}}$</span> but <span class="math-container">$\tilde{\mathbf{q}}\neq\hat{\mathbf{q}}$</span>. The fact that they are different implies (a) <span class="math-container">$\sum \hat q_i&gt;\sum\tilde q_i$</span> and (b) <span class="math-container">$\mathbf{k}^{\prime}\leq\mathbf{k}$</span> and <span class="math-container">$\exists j^*$</span> such that <span class="math-container">$k^{\prime}_{j^{*}}&lt;k_{j^*}$</span>. Let <span class="math-container">$\mathbf{w}=\left(w_{j}\right)_{1\leq j\leq J}$</span>. If <span class="math-container">$\mathbf{Z}$</span> is full rank, the system <span class="math-container">$\mathbf{Z}\mathbf{w}=\mathbf{k}^{\prime}$</span> has a solution. If the solution was such that <span class="math-container">$\mathbf{w}\geq 0$</span> we'd have that <span class="math-container">$\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$</span>. However, I don't know how to prove that indeed <span class="math-container">$\mathbf{w}\geq 0$</span>. In addition, this leaves out the case of a singular <span class="math-container">$\mathbf{Z}$</span>.</li> </ul> <ol start="2"> <li>Let <span class="math-container">$\mathbf{w}=\left(w_{j}\right)_{1\leq j\leq J}$</span> be a vector that (a) is a linear combination of <span class="math-container">$\mathbf{Z}$</span> and (b) is orthogonal to those <span class="math-container">$\mathbf{z}^j$</span> such that <span class="math-container">$k_{j}=k_{j}^{\prime}$</span>. It should be the case that <span class="math-container">$\mathbf{w}^{\top}\mathbf{k}&gt;\mathbf{w}^{\top}\mathbf{k}^{\prime}$</span>. In fact, what needs to happen is that <span class="math-container">$\mathbf{w}$</span> separates <span class="math-container">$\langle \mathbf{Z}\rangle$</span> from the part of <span class="math-container">$\langle \mathbf{A}\rangle$</span> where <span class="math-container">$\mathbf{k}$</span> lies. The underlying rationale is that if the solutions to (I) and (II) are different, <span class="math-container">$\mathbf{k}\not\in\langle \mathbf{Z}\rangle$</span>, while <span class="math-container">$\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$</span>. As <span class="math-container">$\langle\mathbf{Z}\rangle$</span> is convex, we use a separating hyperplane, which is just the specific <em>side</em> of the cone on which <span class="math-container">$\mathbf{k}^{\prime}$</span> sits. The problem is that I don't know how to implement this approach.</li> </ol> <p><strong>Edit 3:</strong></p> <p>All three approaches boil down to proving that <span class="math-container">$\mathbf{k}^{\prime}=\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}\in\langle \mathbf{Z}\rangle$</span>.</p> https://or.stackexchange.com/q/3989 7 Minimum vertex cover and linear programming Mario Giambarioli https://or.stackexchange.com/users/3221 2020-04-25T06:25:32Z 2020-11-24T15:20:29Z <p>Suppose we have a graph <strong>G</strong>. Consider the minimum vertex cover problem of <strong>G</strong> formulated as a linear programming problem, that is for each vertex <span class="math-container">$v_{i}$</span> we have the variable <span class="math-container">$x_{i}$</span>, for each edge <span class="math-container">$v_{i}v_{j}$</span> we have the constraint <span class="math-container">$x_{i}+x_{j}\geq 1$</span>, for each variable we have <span class="math-container">$0\leq x_{i}\leq 1$</span> and we have the objective function <span class="math-container">$\min \sum\limits_{1}^{n}{x_{i}}$</span>. We call such a linear programming problem <em>LP</em>. Note that it is NOT an integer linear programming problem.</p> <p>We find a <a href="https://en.wikipedia.org/wiki/Vertex_cover" rel="nofollow noreferrer">half integral optimal solution</a> of <em>LP</em> that we call <span class="math-container">$S_{hi}$</span>. For each variable <span class="math-container">$x_{i}$</span> that takes value <em>0</em> in <span class="math-container">$S_{hi}$</span>, we add the constraint <span class="math-container">$x_{i}=0$</span> to <em>LP</em>.</p> <p>For each odd cycle of <strong>G</strong>, add to <em>LP</em> the constraint <span class="math-container">$x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$</span> where <span class="math-container">$x_{a},x_{b},x_{c},...,x_{i}$</span> are the vertices of the cycle and <span class="math-container">$k$</span> is the number of vertices of the cycle. We find a new optimal solution of <em>LP</em> that we call <span class="math-container">$S$</span>.</p> <p>If <span class="math-container">$x_{i}$</span> is a variable that takes value <span class="math-container">$0.5$</span> in <span class="math-container">$S_{hi}$</span> and value <span class="math-container">$\gt 0.5$</span> in <span class="math-container">$S$</span>, can we say that there is at least a minimum vertex cover of <strong>G</strong> that contains the vertex associated to <span class="math-container">$x_{i}$</span>?</p> https://or.stackexchange.com/q/3069 13 Categorization of optimization models Luke599999 https://or.stackexchange.com/users/405 2019-11-18T12:02:51Z 2020-11-19T00:42:30Z <p>For many families of optimization problems there is some sort of classification scheme. I am thinking about the triple notation for machine scheduling introduced in <a href="https://www.sciencedirect.com/science/article/abs/pii/S016750600870356X" rel="noreferrer">"Optimization and approximation in deterministic sequencing and scheduling: a survey</a>" by Graham, Lawler, Lenstra, and Kan, or "<a href="http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf" rel="noreferrer">A Compendium on Steiner Tree Problems</a>" by Hauptmann and Karpinski. I wouldn't include something like "Vehicle Routing Problems, Methods, and Applications" by Toth and Vigo, as it focuses on the overview of solution techniques and not so much on a comprehensive list/system to talk about "all" vehicle routing problems.</p> <p>I was wondering, if there was a survey of surveys with the scope of all operations research/combinatorial optimization problems? If not, are there any publications that try something similar (surveys/books of optimization problems with a much broader scope than the examples given)? Or to ask the same question in different words: </p> <p><strong>What are the broadest surveys of operations research/combinatorial optimization problems?</strong></p> https://or.stackexchange.com/q/2927 6 Solving an exponential utility function Mark K https://or.stackexchange.com/users/2440 2019-10-26T09:47:57Z 2020-11-18T17:30:40Z <p>I have a utility function <span class="math-container">$u(x) = a - b e^{-x/20\,000}$</span> and it is given that <span class="math-container">$u(0)=0$</span> and <span class="math-container">$u(100\,000)=1$</span>.</p> <p>I am trying to show that <span class="math-container">$a = 1.0067837$</span> and <span class="math-container">$b = 1.0067837$</span>. Here is what I tried:</p> <p><span class="math-container">\begin{align}u(0) &amp;= a - b e^{-0/20\,000} = 0 &amp;\implies a-be^1=0 &amp;\implies a=be\\u(100\,000) &amp;= a - b e^{100\,000/20\,000} = 1 &amp;\implies a-be^5=1 &amp;\implies a=1+be^5\end{align}</span></p> <p>When <span class="math-container">$a=be=1+be^5$</span>, taking <span class="math-container">$e = 2.72$</span>, it doesn't get <span class="math-container">$b = 1.0067837$</span>.</p> <p>Where did I do wrong, and how can I correct it? Thank you.</p>