Recent Questions - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2019-10-21T05:52:20Z https://or.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/2885 2 partial derivative of LP solution $[x_1 , \ldots x_n]$ w.r.t. $x_i$ or $a_i$ Henry https://or.stackexchange.com/users/2564 2019-10-20T20:48:50Z 2019-10-21T04:39:56Z <p>Suppose I have an optimal solution and I want to know how the solution would (likely) change if one of the coefficients in the objective function changes, or if I add a constraint that forces <span class="math-container">$x_i$</span> away from its optimal value. </p> <p>is there a way to estimate for small changes, without re-running the optimization ?</p> https://or.stackexchange.com/q/2881 3 CPLEX CP Optimizer Java API function missing Maarten https://or.stackexchange.com/users/2562 2019-10-19T23:19:45Z 2019-10-20T01:13:25Z <p>I can not seem to find the needed functions to model the following problem through the Java API (CP Optimizer): a machine that has downtime and sequence-dependent setup times, with the extra constraint, that the physical preparation (setup) of a job ends right before the job starts.</p> <p>Since there are no preemptions, I am using <code>IloIntervalSequenceVar</code> (with a <code>noOverlap</code> that contains the setup time matrix) and <code>IloNumToNumStepFunction</code> for downtimes. This leads to solutions in which a job can start right after a downtime, because the downtime offers enough distance for the transition time to take place (or at least a part of it). The problem is that this transition itself is also an activity, so it is illegal for it to overlap with downtime.</p> <p>Next, I tried modeling the setup times and/or downtimes as intervals themselves, which solves the overlap problem. However, I always bump into the same problem: it is possible to access intervals and their properties after the model has been solved, but not when formulating decision variables. Since setup times are sequence-dependent, I want to assign a certain size to a setup interval, based on its predecessor (its successor is implied through the constraint I mentioned earlier). I have no way of retrieving this. Methods such as <code>getPrev</code> are Native, methods such as <code>prev</code> are Constraints. I basically want a Boolean matrix for each setup interval so I can assign the correct size to it based on the setup time matrix, but I can not find any method that provides this. I can think of ways without modeling setups as intervals, using extra constraints, but they need this same functionality.</p> <p>What do I oversee, is there a better way to go about this?</p> <p>Thanks in advance.</p> https://or.stackexchange.com/q/2879 3 How to make constraints satisfy disciplined convex programming guidelines? Dupin https://or.stackexchange.com/users/2561 2019-10-19T22:13:11Z 2019-10-20T08:34:42Z <p>How do I turn my convex constraints (described below) into constraints that are DCP so that I can solve them in CVXPy? Is there some cheat sheet'' of standard tricks?</p> <p>I'm trying to implement the convex program highlighted in section 3.2 of the paper <em><a href="http://homepage.divms.uiowa.edu/~kvaradar/paps/production.pdf" rel="nofollow noreferrer">Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints</a></em> by Drs. Kamal Jain and Kasturi Varadarajany. I've reduced a model I am working on in my research to a special case of Arrow-Debreu with Constant Returns Technology (AD economy) and would like to implement the constraint satisfaction problem in that paper to run some simulations/find equilibria.</p> <p><strong>In case it is helps, I will describe the convex program specifically in my setting now (depending on the reader, it may be easier to just glance at the paper's section 3). If you'd rather look at the paper skip the bit between lines:</strong></p> <hr> <p>Using CVXPy I am trying to solve a convex program in terms of non-negative variables</p> <ol> <li><span class="math-container">$p_1,...,p_n,p_{n+1},...,p_{n+m}$</span> which represent prices of the goods. Here <span class="math-container">$n$</span> is the number of goods in the AD economy and <span class="math-container">$m$</span> is the number of consumers in the AD economy. They introduce the goods <span class="math-container">$n+1$</span> through <span class="math-container">$n+m$</span> for the sake of writing convex constraints (basically they treat utility as a commodity and force consumers to by their utility from an exclusive producer which produces their utility instead of having them directly buy goods which they derive utility from). I'm implementing this as a vector form CVXPy variable of length <span class="math-container">$n+m$</span>.</li> <li><span class="math-container">$x_{1},...,x_{m}$</span> which, for each consumer <span class="math-container">$i$</span>, represents the demand of that consumer for good <span class="math-container">$n+i$</span>. As I described briefly in above, consumers have utility only for a good representing their own utility which a special producer will produce for them and they will sell their endowments to maximize the amount of this good they receive. I'm implementing this as a vector CVXPy variable of length <span class="math-container">$m$</span>.</li> <li><span class="math-container">$z_1,...,z_{n+m}$</span> which, for each producer <span class="math-container">$k$</span>, is a vector <span class="math-container">$z_k = (z_{k1},...,z_{kn})$</span> describing the inputs used by the <span class="math-container">$k^{th}$</span> producer. Note that, each producer has a function (described in the convex program below) describing how to turn these input into output. I'm implementing this as a matrix CVXPy variable of dimensions <span class="math-container">$(n+m, n)$</span>.</li> <li><span class="math-container">$q_1,...,q_{n+m}$</span> which, for each producer <span class="math-container">$k$</span>, is the scalar output of their production function (which outputs only good <span class="math-container">$j$</span>). In other words, this variable described <span class="math-container">$q_k = f_k(z_k)$</span>. I'm implementing this as a vector CVXPy variable of length <span class="math-container">$n+m$</span>.</li> </ol> <p>I'm writing the convex program as:</p> <p><span class="math-container">$\text{minimize } 1$</span></p> <p><span class="math-container">$\text{subject to } p_{n+i}x_{i} \geq \sum\limits_{j=1}^{n} p_{j} E_{ij} \text{, for } 1 \leq i \leq m$</span></p> <p><span class="math-container">$\hspace{2cm} q_k \leq \sum\limits_{j=1}^{n} z_{kj} \text{, for } 1 \leq k \leq n$</span></p> <p><span class="math-container">$\hspace{2cm} q_{n+k} \leq \left(\sum\limits_{j=1}^{n} U_{kj} z_{(n+k),j}^{\rho}\right)^{\frac{1}{\rho}} \text{, for } 1 \leq k \leq m$</span></p> <p><span class="math-container">$\hspace{2cm} p_k \leq A_{kj} \cdot p_{j} \text{, for } 1 \leq k \leq n \text{ and for } 1 \leq j \leq n$</span></p> <p><span class="math-container">$\hspace{2cm} p_{n+k}^{1-\frac{1}{1-\rho}} \geq \sum\limits_{j=1}^{n} U_{kj}^{\frac{1}{1-\rho}} p_{j}^{1-\frac{1}{1-\rho}} \text{, for } 1 \leq k \leq m$</span></p> <p><span class="math-container">$\hspace{2cm} \sum\limits_{k=1}^{n+m} z_{kj} \leq q_j + \sum_{i=1}^{m} E_{ij} \text{, for } 1 \leq j \leq n$</span></p> <p><span class="math-container">$\hspace{2cm} x_i \leq q_{n+i} \text{, for } 1 \leq i \leq m$</span></p> <p>Where <strong><span class="math-container">$E$</span></strong> is a constant matrix of dimension <span class="math-container">$(m,n)$</span> denoting the consumers' initial "endowment" of goods, <strong><span class="math-container">$U$</span></strong> is a constant matrix of dimension <span class="math-container">$(m,n)$</span> denoting the utility coefficient of each good for each consumer, <strong><span class="math-container">$\rho$</span></strong> is a scalar constant on the open interval <span class="math-container">$[0,1]$</span> which describes the "elasticity of substitution" in the economy, and finally <strong><span class="math-container">$A$</span></strong> is a constant binary matrix (used to encode a "local" notion on goods).</p> <p>Finally, notice that when we make the substitution <span class="math-container">$p_j = e^{\psi_j}$</span> in these constraints all of them become convex. </p> <hr> <p>After writing this into CVXPy (with the substitution to <span class="math-container">$e^{\psi_j}$</span> done), I am having problems in the first constraint with <span class="math-container">$p_{n+i}x_{i}$</span> not being dcp, in the third constraint where the CES (constant elasticity of substitution) utility function is not dcp, and in the fifth constraint since again the CES function is not dcp.</p> <p>Could anybody help me massage these three sub-expressions into dcp sub-expressions? I'm at a loss and this would be a huge help! Thanks! </p> <p>Some Notes: - By DCP I mean "Disciplined Convex Programming." More info can be found <a href="https://www.cvxpy.org/tutorial/dcp/index.html" rel="nofollow noreferrer">here</a>. - You may have noticed that in my AD economy I have exactly <span class="math-container">$n$</span> producers and <span class="math-container">$n$</span> goods (i.e. one producer per good that produces an amount of it's output good exactly equal to the sum of the amount of other goods it take as input). In reality there are fewer producers than goods, but explaining this number is rather involved (it comes out of the proof that my model reduces to it, but it shouldn't affect anything in this case.) </p> https://or.stackexchange.com/q/2877 7 Modeling the Choose function Josh Allen https://or.stackexchange.com/users/2513 2019-10-19T20:20:23Z 2019-10-20T12:44:20Z <p>In statistics, one often encounters the choose function <span class="math-container">${x \choose y}$</span> which encodes the number of ways of choosing <span class="math-container">$y$</span> items from a set of <span class="math-container">$x$</span> items. How would one go about modeling a choose equality constraint</p> <p><span class="math-container">$${x \choose y} = C$$</span></p> <p>without explicitly using the factorial-based formulation (if possible)? </p> https://or.stackexchange.com/q/2875 6 Doubt on finding simplex's initial canonical tableau (II Phase) Johnny Bueti https://or.stackexchange.com/users/2559 2019-10-19T16:04:38Z 2019-10-19T20:26:04Z <p>Good day.</p> <p>Given the following notation for an initial canonical tableau for a linear program in standard form:</p> <p><span class="math-container">$$T_1 = \begin{bmatrix} I &amp; B^{-1}N &amp; \bar{x}_{B} \\ 0^\intercal &amp; \hat{x}_{N}^\intercal &amp; -\bar{z} \end{bmatrix}$$</span></p> <p>with: </p> <ul> <li><span class="math-container">$B$</span> representing the matrix of the basic technological coefficients (<span class="math-container">$x_{ij})$</span>,</li> <li><span class="math-container">$N$</span> representing the matrix of the non-basic tech. coefficients,</li> <li><span class="math-container">$\bar{x}_{B}$</span> representing the <code>B</code>-partition of the given feasible basic solution,</li> <li><span class="math-container">$\hat{x}_{N}^\intercal$</span> representing the vector of the non-basic reduced costs,</li> <li><span class="math-container">$\bar{z}$</span> representing the value of the objective function at the given <span class="math-container">$\bar{x}$</span> solution.</li> </ul> <p>how would you go about representing the following standard linear program in tableau form?</p> <p><span class="math-container">\begin{alignedat}{4} \min_x{z} = &amp; \; -4x_1 &amp; \; -3x_2 &amp; \; +7x_3 \\ &amp; \; \quad\ 3x_1 &amp; \; -5x_2 &amp; \; +4x_3 &amp; \; + x_4 &amp;&amp; = &amp; \; 3 \\ &amp; \; \quad\ 6x_1 &amp; \; +4x_2 &amp; \; -5x_3 &amp; &amp; \; +x_5 \ &amp; = &amp; \; 2 \\ &amp;&amp;&amp;&amp;&amp; \quad\ \ x &amp; \ge &amp; \; 0 \end{alignedat}</span> </p> <p><strong>Update (adding what I have already tried/already know and tried to apply)</strong>: looking for help on manuals and here on OR SE alike, the tableau seems to be generally in the form:</p> <p><span class="math-container">$$T_2 = \begin{bmatrix} A &amp; b \\ c^\intercal &amp; -\bar{z} \end{bmatrix}$$</span></p> <p>with <span class="math-container">$A$</span> being the matrix of all technological coefficients, <span class="math-container">$b$</span> the resources vector and <span class="math-container">$c^\intercal$</span> the transpose costs vector. </p> <p>The problem does <strong>not</strong> give you an initial <span class="math-container">$\bar{x}$</span> solution and I don't personally know how to represent the program above in tableau form. </p> <p>Is the following correct? If so, why is <span class="math-container">$T_1 = T_2$</span>? </p> <p><span class="math-container">$$\bar{T} = \begin{bmatrix} 3 &amp; -5 &amp; 4 &amp; 1 &amp; 0 &amp; 3 \\ 6 &amp; 4 &amp; -5 &amp; 0 &amp; 1 &amp; 2 \\ -4 &amp; -3 &amp; 7 &amp; 0 &amp; 0 &amp; 0 \end{bmatrix}$$</span></p> <p>The tableau above is built supposing that <span class="math-container">$x_4, x_5$</span> is the feasible basic solution vector and that, then, the tableau is in canonical form with respect to <span class="math-container">$\bar{x} = \begin{bmatrix} 0 &amp; 0 &amp; 0 &amp; 3 &amp; 2 \end{bmatrix}$</span>. </p> https://or.stackexchange.com/q/2874 10 What Is OR Research Like? D.Gray https://or.stackexchange.com/users/547 2019-10-19T15:16:37Z 2019-10-19T16:33:44Z <p>I am working on my MSc thesis right now which is in resource economics, but I have ended up actually operating mostly in the realm of OR and learning about programming, algorithms, optimization problems, some complexity theory, and a bit of machine learning, and I find it all pretty interesting. My thesis project is more or less an application of OR on a particular real world application, but I enjoy it and I think that it could potentially be a fun field to pursue.</p> <p>However, I am curious what research in OR is actually like as opposed to simply applying OR concepts and techniques to a particular problem. With that being said, what are some areas that OR scientists actually do research in? What are some current topics currently being worked on and why, and is OR research more about developing algorithms to solve things like MINLPs or is it more about application?</p> https://or.stackexchange.com/q/2873 6 If-then constraints in MIP programming Qbik https://or.stackexchange.com/users/2557 2019-10-19T10:42:59Z 2019-10-20T00:59:24Z <p>For continuous variables <span class="math-container">$x$</span> and <span class="math-container">$y$</span>, the constraints are:</p> <pre><code>if x &gt;= 0 and x &lt; 1 then y &lt;= 10 and if x &gt;= 1 and x &lt; 2 then y &lt;= 5 and (up to the ten lines of inequalities) if x &gt;= 2 then y &lt;= 2 </code></pre> <p>The problem is on modeling nonlinear behaviour of gas storage pumping efficiency, which decreases for high load in case of very large gas storages (decrease is seen for storages with capacity above 5 million cubic meters). I have to write these constrains using MIP (or LP) formulation. I can use SOS1/SOS2 variables in GAMS with cplex/gurobi solvers.</p> https://or.stackexchange.com/q/2871 5 How to formulate a MIP that can minimize the costs with a combination of subsets given a set? Harry van t Kamp https://or.stackexchange.com/users/2555 2019-10-19T10:09:27Z 2019-10-19T17:35:13Z <p>I am trying to solve the following problem. I have a set <span class="math-container">$\{1,2,3\}$</span>, which gives the following subsets with its costs:</p> <p><span class="math-container">$\{1\}=8$</span>, <span class="math-container">$\{2\}=9$</span>, <span class="math-container">$\{3\}=7$</span>, <span class="math-container">$\{1,2\}=9$</span>, <span class="math-container">$\{1,3\}=18$</span>, <span class="math-container">$\{2,3\}=15$</span> and <span class="math-container">$\{1,2,3\}=24$</span>.</p> <p>Which combinations of subsets give the cheapest option, so that every element is in one the subsets only once?</p> <p>For this example the solution would be: <span class="math-container">$\{1,2\}$</span> and <span class="math-container">$\{3\}$</span>, with a total cost of <span class="math-container">$16$</span>.</p> <p>I want to formulate this as a mixed-integer programming problem, any suggestions?</p> https://or.stackexchange.com/q/2869 7 Was there something specific that caused graph cuts to lose popularity in the last 5 years? user1271772 https://or.stackexchange.com/users/727 2019-10-18T23:37:10Z 2019-10-19T08:15:31Z <p>Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago:</p> <p><a href="https://i.stack.imgur.com/h0b7X.png" rel="noreferrer"><img src="https://i.stack.imgur.com/h0b7X.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/JwWOV.png" rel="noreferrer"><img src="https://i.stack.imgur.com/JwWOV.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/n72Lc.png" rel="noreferrer"><img src="https://i.stack.imgur.com/n72Lc.png" alt="enter image description here"></a></p> <hr> <p>For privacy I've cut the all author names out, but it seems that the people who published several graph-cut papers have the same (highly unusual) downward citation trend:</p> <p><a href="https://i.stack.imgur.com/AHgA0m.png" rel="noreferrer"><img src="https://i.stack.imgur.com/AHgA0m.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/ptjecm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ptjecm.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/Y54Wgm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Y54Wgm.png" alt="enter image description here"></a> <a href="https://i.stack.imgur.com/VlCKcm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/VlCKcm.png" alt="enter image description here"></a></p> <hr> <p>These trends are highly uncommon in academia (if not only completely uncommon except for in this unique case). What happened to the field of graph-cuts? Is some rising new interest such as Deep Learning provably better for the most popular application, in almost every way? Has something made graph-cuts obsolete for the most popular applications?</p> https://or.stackexchange.com/q/2866 6 How to tackle large nurse scheduling problem? Stradivari https://or.stackexchange.com/users/991 2019-10-18T14:56:31Z 2019-10-18T19:49:29Z <p>I have a nurse-scheduling type of problem with a time span of a year and many employees. </p> <h2>Formulation</h2> <p>My main variables are: <span class="math-container">\begin{align}x_{e,t} &amp;= \begin{cases}1 \text{ if employee } e \text{ is assigned to task } t \\ 0 \text{ otherwise} \end{cases}\\w_{e,d} &amp;= \begin{cases}1 \text{ if employee } e \text{ is assigned to any task in day } d \\ 0 \text{ otherwise} \end{cases}\\v_{e,d} &amp;= \begin{cases}1 \text{ if employee } e \text{ is on vacation on day } d \\ 0 \text{ otherwise} \end{cases}\end{align}</span> Hired days: <span class="math-container">$$H_{e} = \text{last work day}-\text{first work day}$$</span> Employee vacations: <span class="math-container">$$V_{e} = \left\lceil\frac{H_{e}\cdot31}{366}\right\rceil$$</span></p> <h2>Details</h2> <ul> <li>I cannot divide the problem more in terms of time as there are some constraints and variables that need to be calculated yearly.</li> <li>I have the following symmetry breaking constraint: <span class="math-container">$$\sum_{t\in T}{x_{e,t}} \le \sum_{t\in T}{x_{e-1,t}}$$</span></li> <li>I have divided the problem into <a href="https://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="noreferrer">cliques</a> of related tasks and employees.</li> <li>I can provide more details about my variables and constraints if needed.</li> </ul> <h2>Question</h2> <p>Is there a better way to formulate this problem?</p> <p>Maybe I could add more symmetry breaking or redundant constraints that could speed up the solving (I'm using OR-Tools).</p> <p>I also feel like I should assign group of tasks instead of individual tasks, is that a good idea?</p> <p>Edit:</p> <p>With this formulation I have around 159245 variables and 478303 constraints with 80 employees.</p> https://or.stackexchange.com/q/2862 10 Tool/Editor to visualize optimization problem files and solutions JaBe https://or.stackexchange.com/users/1008 2019-10-18T12:51:20Z 2019-10-20T04:54:56Z <p>Is there a tool with a graphical user interface which helps to visualize optimization problem files (e.g. lp/mps) and solutions?</p> <p>Let's say you have an optimization problem and a solution and want to be able to track individual variables, solution values, maybe even dual values and so on. For example, to click on a variable and see all containing rows. Or to select a row and highlight all variables which are in the row. Or even to fuse the information of an solution with the lp file so that you can see all variables and their solution value in the problem. </p> <p>My working method is to use Notepad++, highlight variable names or searching for variable names and clicking through the files and copying individual rows to a new text file...</p> https://or.stackexchange.com/q/2861 5 Maximize charging, minimize cost user2974951 https://or.stackexchange.com/users/2550 2019-10-18T12:49:55Z 2019-10-18T13:41:20Z <p>The task pertains to choosing an algorithm based on the data, requirements and constraints.</p> <p>I have a number of electrical devices (<span class="math-container">$d_1,d_2,\dots,d_n$</span>) with batteries. Throughout the day I will receive these devices with arbitrary battery storage (from 0 to 100%). Batteries have varying capacity. My job is to refill the batteries.</p> <p>I have to consider the price of charging these devices (cost per unit), since the price of charging a device changes throughout the day, for each day we have 24 different prices for 24 different intervals (<span class="math-container">$c_1,c_2,\dots,c_{24}$</span>).</p> <p>My goal is to charge these devices optimally, that is determine how much to charge each available device for each time interval in the future, while minimizing the cost of charging them, while also taking into account that I have a limited amount of charging capacity (upper bound) at any one time at <span class="math-container">$x$</span> units.</p> <p>Ideally I would like to run this each time I get a new device, to get the current optimal solution. If possible, I would like to avoid having sharp peaks of aggressive charging followed by low (no) charging.</p> <p>What kind of algorithm can I use for this task? How would I formulate it? Can LP be used for this?</p> https://or.stackexchange.com/q/2859 5 Logical Constraints Modelling using Big-M formulation memop https://or.stackexchange.com/users/2548 2019-10-18T12:20:22Z 2019-10-19T08:03:07Z <p>I am trying to model some logical constraints in ILOG. Logical constraints could be given such as: </p> <ul> <li><p>Constraint 1 or Constraint 2, </p></li> <li><p>Constraint 3 or Constraint 4,</p></li> <li><p>Constraint 5 or Constraint 6. </p></li> </ul> <p>The six constraints in question are listed below. <span class="math-container">\begin{align}&amp;\,\,\sum_{s=1}^Sx_{is}=1\quad\forall i\in T\\\text{Constraint}\,1:&amp;\,\,\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{js}&amp;=0&amp;\quad(i,j)\in\text{linked}\\\text{Constraint}\,2:&amp;\,\,\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{j(2\cdot m-s)}&amp;=0&amp;\quad(i,j)\in\text{linked}\\\text{Constraint}\,3:&amp;\,\,\left\vert\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{js}\right\vert&amp;\ge d_1&amp;\quad(i,j)\in\min\\\text{Constraint}\,4:&amp;\,\,\left\vert\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{j(2\cdot m-s)}\right\vert&amp;\ge d_1&amp;\quad(i,j)\in\min\\\text{Constraint}\,5:&amp;\,\,\left\vert\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{js}\right\vert&amp;\le d_2&amp;\quad(i,j)\in\max\\\text{Constraint}\,6:&amp;\,\,\left\vert\sum_{s=1}^Ss\cdot x_{is}-\sum_{s=1}^Ss\cdot x_{j(2\cdot m-s)}\right\vert&amp;\le d_2&amp;\quad(i,j)\in\max\end{align}</span> Only one of the constraints in each group should be satisfied and active, i.e if Constraint 1 is active, Constraint 2 should not be active, or vice versa. </p> <p>I have tried some logical constraints definition method, e.g. Big M method, but I could not define the constraints and run the model. Since there are too many sum functions in my model, it is very challenging to build a big-M model. So I need your help. </p> <p>I would appreciate it if you have any suggestions. Thank you in advance. Regards.</p> https://or.stackexchange.com/q/2858 6 DOCPLEX: tips to manipulate data input (binary parameter) campioni https://or.stackexchange.com/users/2453 2019-10-18T09:24:38Z 2019-10-18T13:05:57Z <p>I am coding a MIP problem in docplex and I would like to ask for some tips.</p> <p>I would like to input a binary <strong>parameter</strong> that states a compatibility relation:</p> <p>I have a set of characteristics <span class="math-container">$H$</span> to be satisfied in a product. The product is made by a set of components <span class="math-container">$C$</span> and each component can have many variants <span class="math-container">$V$</span>. For stating the compatibility between variant of component and required characteristics, I stated the following binary parameter: </p> <ul> <li><span class="math-container">$G_h{_{c}}_{v}=1$</span> if the characteristic <span class="math-container">$c$</span> can be accomplished by variant <span class="math-container">$v$</span> of component <span class="math-container">$c$</span>, and zero otherwise</li> </ul> <p>I was wandering to use a 3D numpy array to state this relation. But I if I'm not wrong, I did not find examples using 3D numpy array. Instead, I saw <code>namedTuple</code>, that I guess was used to state similar relation for string elements. </p> <p>How can I code binary parameters in docplex keeping the index of each element, by accessing the value of each parameter and also its key ?</p> <p>If someone could help me, I will be very grateful.</p> https://or.stackexchange.com/q/2855 7 Graphical method in linear programming Mark K https://or.stackexchange.com/users/2440 2019-10-18T03:55:39Z 2019-10-18T09:17:41Z <p><a href="https://accounting-simplified.com/management/limiting-factor-analysis/linear-programming/graphical-example.html" rel="nofollow noreferrer">This page</a> describes the graphical method to solve a linear program. The formulation is as follows.</p> <p><span class="math-container">\begin{alignat}{2} \max &amp;\quad Z = 200W + 100B\\ \text{s.t.} &amp;\quad 1W + 0.8B &amp;&amp;\leq 4000\\ &amp;\quad 0.004W + 0.001B &amp;&amp;\leq 10\\ &amp;\quad W, B &amp;&amp;\geq 0\end{alignat}</span></p> <p><a href="https://i.stack.imgur.com/ALS9T.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ALS9T.png" alt="Graph is:"></a></p> <p>The solution given is:</p> <blockquote> <p>Co-ordinates of the optimum point are approximately 1850 W and 2750 B (1850, 2750).</p> </blockquote> <p>What would be an easy way to calculate the optimal solution in addition to an estimate seen from graph (rather than the simplex method)? Thank you.</p> https://or.stackexchange.com/q/2854 7 Solving large-scale stochastic mixed integer program S_Scouse https://or.stackexchange.com/users/2546 2019-10-17T17:00:11Z 2019-10-17T18:24:29Z <p>What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the problem in consideration is not bilevel). I am actually looking for general ways/guidelines to tackle these types of problems that are hard to solve even with a large optimality gap but do have an optimal solution.</p> https://or.stackexchange.com/q/2847 6 Having trouble with objective function in Python: "GurobiError: Variable not in model". What else could I try? Jacob Myer https://or.stackexchange.com/users/2393 2019-10-16T22:43:23Z 2019-10-17T07:32:05Z <p>I am trying to figure out how I can write this objective function into python using Gurobi. I have to minimize the sum of the product of three dictionary's values. The reason I am confused is that while the first two dictionaries I am multiplying are the same length (somewhere in the thousands), the third has only 12 items. Also the first two dictionaries have tuple keys and the third does not. </p> <p>The first dictionary <code>ASSG</code> is a decision variable that has the format: </p> <pre class="lang-py prettyprint-override"><code>ASSG = {('Abilene, TX', 'Boston, MA'): &lt;gurobi.Var ASSG[Abilene, TX,Boston, MA]&gt;, ('Abilene, TX', 'Chicago, IL'): &lt;gurobi.Var ASSG[Abilene, TX,Chicago, IL]&gt;, ('Abilene, TX', 'Dallas, TX'): &lt;gurobi.Var ASSG[Abilene, TX,Dallas, TX]&gt;, ('Abilene, TX', 'Denver, CO'): &lt;gurobi.Var ASSG[Abilene, TX,Denver, CO]&gt;, ...} </code></pre> <p>The second dictionary is <code>miles</code> and it has the following format:</p> <pre class="lang-py prettyprint-override"><code>miles = {('Abilene, TX', 'Boston, MA'): 2091.92, ('Abilene, TX', 'Chicago, IL'): 1148.37, ('Abilene, TX', 'Dallas, TX'): 189.87, ('Abilene, TX', 'Denver, CO'): 775.6, ...} </code></pre> <p>The third dictionary is called <code>Demand</code> and it looks like:</p> <pre class="lang-py prettyprint-override"><code>Demand = {'Boston, MA': 1051, 'Chicago, IL': 940, 'Dallas, TX': 1131, 'Denver, CO': 466, 'Los Angeles, CA': 1301, 'Richmond, VA': 1171, 'Miami, FL': 1463, 'New York, NY': 1120, 'Phoenix, AZ': 665, 'Pittsburgh, PA': 1280, 'San Fransisco, CA': 615, 'Seattle, WA': 528} </code></pre> <p>I think what I need to do is multiply all of the values where the keys in <code>Demand</code> match the second element in the tuple of <code>ASSG</code> and <code>miles</code>'s keys. i.e. All the items with <code>'Boston, MA'</code> get multiplied, all the Chicagos, all the Dallases... </p> <p>I have tried multiplying them separately and then using quicksum but I receive an error:</p> <pre class="lang-py prettyprint-override"><code>a = {k: ASSG[k]*miles[k] for k in ASSG} b = {k:Demand.get(k, 1)* v for k,v in x.items()} m.setObjective(quicksum(b.values())) m.ModelSense = GRB.MINIMIZE m.update() GurobiError: Variable not in model </code></pre> https://or.stackexchange.com/q/2846 9 Where to search for PhD level jobs in OR? Rostov https://or.stackexchange.com/users/2541 2019-10-16T22:30:49Z 2019-10-17T15:28:54Z <p>I started hunting for jobs and I'm not sure what are good websites I should be keeping an eye on. I'm interested mainly in Europe.</p> https://or.stackexchange.com/q/2837 7 How can I add this conditional constraint to my model in Python? Jacob Myer https://or.stackexchange.com/users/2393 2019-10-16T04:31:18Z 2019-10-16T14:20:51Z <p>I am creating an optimization model with 2 sets of binary decision variables. The first, <code>site</code>, is regarding which of 380 cities to place manufacturing sites in, and the second, <code>ASSG</code> is regarding which of 12 cities each manufacturing site will be assigned to service. There will be 3 manufacturing sites total. </p> <p>I need to add a constraint that the sum of all cities serviced by a <em>potential</em> manufacturing site is the number of cities that need serviced, <code>12</code>, but this limit needs to be <code>0</code> if a manufacturing site is not placed in that location. </p> <p>This is difficult for me to explain so I've included a screenshot of the Excel model I am trying to scale-up using Python. The "Logical constraint" is what I am trying to code into Python:</p> <p><a href="https://i.stack.imgur.com/qLrmc.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qLrmc.png" alt="enter image description here"></a></p> <p>I know this code is a bit of a mess, I'm not great with dictionaries and there's too much going on here for me to keep track of it, but this is what I have so far:</p> <pre class="lang-py prettyprint-override"><code>site = m.addVars(siteLoc, vtype=GRB.BINARY, name='site') # siteLoc is a list of 380 potential mfg site locations ASSG = m.addVars(siteASSG, vtype=GRB.BINARY, name='ASSG') # siteASSG is a gurobi tuplelist of the format: (potential mfg site location, one of 12 cities mfg site will service) m.update() m.addConstr(sum(val for key, val in ASSG.items() if key == k for k in site.keys()) &lt;= 12 * val for key, val in site.items()) </code></pre> https://or.stackexchange.com/q/2836 7 Buyback policy in a supply chain Harry https://or.stackexchange.com/users/2535 2019-10-16T02:59:10Z 2019-10-17T04:35:50Z <p>Consider a three level supply chain consisting of a manufacturer, a wholesaler and a retailer. Suppose I wish to include a buyback contract to this network. Then am I right when I say that wholesaler buys unsold items from the retailer at a specific buyback price. Similar is the case between manufacturer and wholesaler. But what does a manufacturer do with unsold goods? Suppose the product is perishable say a food item.</p> https://or.stackexchange.com/q/2828 12 Is This Constraint Convex? D.Gray https://or.stackexchange.com/users/547 2019-10-15T15:54:22Z 2019-10-17T15:45:58Z <p>I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning as to why I think it's convex. Hopefully the holes in my thinking can be pointed out and corrected. </p> <p><span class="math-container">$$X_{t} = \frac{ Y_{t-1}^2 }{Y_{t-1}^2 + a^2}Z_{t-1}, \quad t=1,2,\dots,T \tag1$$</span> <span class="math-container">$$X_t,Y_t,Z_t \ge 0,$$</span> <span class="math-container">$$X_0, Y_0, Z_0, \alpha \gt 0$$</span></p> <p><strong>Argument 1:</strong> A quadratic polynomial is convex, so if the constraint was simply <span class="math-container">$X_{t} = Y_{t-1}^2$</span> then the constraint would be convex.</p> <p><strong>Argument 2:</strong> By a similar extension, <span class="math-container">$X_{t} = Y_{t-1}^2 + \alpha^2$</span> would be convex. </p> <p><strong>Argument 3:</strong> The ratio of two convex functions, call it <span class="math-container">$F_{t-1}$</span>, should also be convex. </p> <p><strong>Argument 4:</strong> If <span class="math-container">$F_{t-1}$</span> is convex, then multiplying <span class="math-container">$F_{t-1}$</span> by a continuous linear variable would not impose any non-convexity issues. </p> <p><strong>Conclusion:</strong> The original constraint is convex but not affine and as such we can apply a relaxation to change the problem into:</p> <p><span class="math-container">$$X_{t} \le \frac{ Y_{t-1}^2 }{Y_{t-1}^2 + a^2}Z_{t-1}, \quad t=1,2,\dots,T \tag1$$</span></p> https://or.stackexchange.com/q/2741 18 PhD-level textbooks on linear programming tiger123 https://or.stackexchange.com/users/2467 2019-10-05T01:47:03Z 2019-10-17T07:47:01Z <p>My graduate Linear Programming class uses Bertsimas &amp; Tsitsiklis's <a href="http://www.athenasc.com/linoptbook.html" rel="nofollow noreferrer">Introduction to Linear Optimization</a>. Are there any alternative texts that I could use to supplement this textbook (mainly the content of Chapter 2 of Bertsimas &amp; Tsitsiklis: extreme point, vertex, basic feasible solution, contains/does not a line, Fourier-Motzkin) at the same level rigor and which contain exercises that I could practice on? </p> <p>Ideally, I would also like a book with a decent (the more the better) number of pictures that gives geometric intuition behind proofs. Thanks.</p> https://or.stackexchange.com/q/2612 7 Solutions to a parametrized optimization problem Patricio https://or.stackexchange.com/users/2391 2019-09-21T15:48:53Z 2019-10-16T21:11:02Z <p>I have the following maximization program</p> <p><span class="math-container">\begin{align} \max\limits_{\{q_i\}}&amp;\quad\sum\limits_{i=1}^nq_i \\ \text{s.t.}&amp;\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \alpha}x_{ij} &amp; j=\{1,\dots,J\} \\ q_i \geq 0 &amp; i=\{1,\dots,n\} \\ \end{cases} \end{align}</span></p> <p>with <span class="math-container">$\alpha&gt;0$</span>, <span class="math-container">$x_{ij}\geq 0$</span> and <span class="math-container">$k_j \geq 0$</span> for all indices. I'd like to prove that if <span class="math-container">$\mathbf q^*=(q_1^*,\dots,q_n^*)$</span> is a solution to this problem for <span class="math-container">$\mathbf k^*=(k_1^*,\dots,k_J^*),$</span> then <span class="math-container">$\delta^{\alpha}\mathbf q^*$</span> is a solution for <span class="math-container">$\delta \mathbf k^*.$</span></p> <p>I proceed by contradiction: </p> <p>Assume that the solution for <span class="math-container">$\delta \mathbf k^*$</span> was <span class="math-container">$\mathbf {\hat q}$</span> and such that <span class="math-container">$\sum\limits_{i=1}^n \hat q_i&gt;\delta^{\alpha}\sum\limits_{i=1}^n q_i^*$</span>. Consider <span class="math-container">$\mathbf {\bar q}=\dfrac1{\delta^{\alpha}}\mathbf {\hat q}.$</span> It is easily seen that <span class="math-container">$\mathbf {\bar q}$</span> is feasible for <span class="math-container">$\mathbf k^*$</span>. But we have that</p> <p><span class="math-container">$$\sum_{i=1}^n \bar q_i&gt;\sum_{i=1}^n q_i^*,$$</span></p> <p>so <span class="math-container">$\mathbf q^*$</span> cannot be a solution for <span class="math-container">$\mathbf k^*$</span>.</p> <p>Is this correct? I worry that if the program has multiple solutions (and this can be the case when <span class="math-container">$\alpha&gt;1$</span>) my proof is not general enough or even wrong altogether.</p> <p><strong>Edit:</strong> Perhaps it would be more accurate to say that, letting <span class="math-container">$\mathbf S(\mathbf k)$</span> denote the set of solutions to the maximization program for a given <span class="math-container">$\mathbf k$</span>, <span class="math-container">$$\mathbf q^*\in \mathbf S(\mathbf k^*) \iff \delta^{\alpha}\mathbf q^*\in \mathbf S(\delta\mathbf k^*)$$</span></p> https://or.stackexchange.com/q/1386 10 Expressing an implication as ILP where each implication term comprises a chain of boolean ORs ephemeral https://or.stackexchange.com/users/584 2019-08-26T12:17:10Z 2019-10-19T15:43:34Z <p>Consider an implication of the form <span class="math-container">$A \implies B$</span> where both <span class="math-container">$A, B$</span> comprises a chain of Boolean OR variables. For example, <span class="math-container">$(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$</span>. How can this be expressed as an ILP? All variables are Boolean.</p> <p>I have derived the following using CNF, however it turns out to be non-linear, can this be expressed in Linear Form?</p> <p>Let us suppose <span class="math-container">$A = \{ a_1, a_2, a_3\}$</span> and <span class="math-container">$B = \{ b_1, b_2, b_3\}$</span>. thus,</p> <p><span class="math-container">\begin{equation} \bigvee A \implies \bigvee B \\ \overline{\bigvee A} \bigvee \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} \overline a\right) \bigvee \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} (1-a)\right) \bigvee \left(\bigvee B\right) \\ \left(\prod_{a \in A} (1-a)\right) \bigvee \left(\sum_{b \in B} b\right) \\ \prod_{a \in A} (1-a) + \sum_{b \in B} b \geq 1 \end{equation}</span></p> <p>Thus, thus leads to <span class="math-container">$(1-a_1)(1-a_2)(1-a_3) + b_1 + b_2 + b_3 \geq 1$</span>, which essentially leads to a product of complements of the variables in <span class="math-container">$A$</span>. Can this be expressed in terms of linear constraints?</p> https://or.stackexchange.com/q/1367 15 Divisibility constraints in integer programming Andrei Smolensky https://or.stackexchange.com/users/1231 2019-08-23T22:43:58Z 2019-10-19T15:45:59Z <p>In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer programming problem, where one of the constraints is a divisibility assumption. Namely, for the variables <span class="math-container">$x_i\in\mathbb{Z}_{\geqslant0}$</span> this constraint is of the form <span class="math-container">$$Q(x_1,\ldots,x_n)\quad \text{divides}\quad L(x_1,\ldots,x_n),$$</span> where <span class="math-container">$L$</span> is linear and <span class="math-container">$Q$</span> is quadratic. (for completeness: the function to minimize is simply <span class="math-container">$\sum x_i$</span>, and other constraints are <span class="math-container">$P(x_i)&gt;0$</span> for some quadratic <span class="math-container">$P$</span> and <span class="math-container">$(x_1,\ldots,x_n)$</span> is not an integer linear combination of some given integer vectors)</p> <p>I don't reckon there is an out-of-the-box solution for this, so I wonder if someone has considered any other problems of this sort, say, where there is a constraint of the form "<span class="math-container">$L_1(x_i)$</span> divides <span class="math-container">$L_2(x_i)$</span>" for some linear <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span>?</p> https://or.stackexchange.com/q/1265 15 Modeling the uncertainty of the input parameters Mehdi https://or.stackexchange.com/users/172 2019-08-13T14:07:34Z 2019-10-20T13:01:45Z <p>There are many approaches to deal with the uncertainty such as stochastic programming, robust optimization and fuzzy programming. Finding a suitable approach that is applicable in the real situations can be tricky.</p> <p>I have two main questions:</p> <p>1- In general, what are the conditions to use Stochastic Programming in favor of Robust Optimization? </p> <p>2- When we should model the uncertain parameters with discrete scenarios instead of their probability distributions?</p> https://or.stackexchange.com/q/599 10 Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location ydubey7 https://or.stackexchange.com/users/606 2019-06-19T00:41:00Z 2019-10-20T12:59:04Z <p>In <a href="http://pages.cs.aueb.gr/~markakis/research/jacm03-facloc.pdf" rel="nofollow noreferrer">Jain <em>et al.</em> (2003)</a><sup>1</sup>, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap <span class="math-container">$\Omega\left(\frac{\log n}{\log \log n}\right)$</span>. The algorithm is as follows:</p> <p>Construct an instance of set cover, where the ground set of elements is the set of clients <span class="math-container">$D$</span> and the set system contains all sets of the form <span class="math-container">$(i,A)$</span> where <span class="math-container">$i \in F$</span> is a facility and <span class="math-container">$A \subseteq D$</span> is a set of clients. Set <span class="math-container">$(i,A)$</span> covers the elements in <span class="math-container">$A$</span> and <span class="math-container">$\operatorname{cost}(i,A) = f_i + \sum{d_{ij}}$</span>. The greedy algorithm is to choose the set <span class="math-container">$(i,A)$</span> that minimizes <span class="math-container">$\frac{\operatorname{cost}(i,A)}{|A\,\cap\, \text{uncovered}|}$</span>. This can be done in polytime by iterating through the facilities <span class="math-container">$i \in F$</span> and through <span class="math-container">$s = 1,\ldots,|\text{uncovered}|$</span> and considering <span class="math-container">$A$</span> to be the <span class="math-container">$s$</span> closest uncovered clients to facility <span class="math-container">$i$</span>.</p> <p>Part of the proof of Jain <em>et al.</em><sup>1</sup> is to claim that (on the instance they construct) the above greedy algorithm will open all <span class="math-container">$k$</span> facilities, while the optimal thing to do is to open only one of the facilities. <strong>I can't seem to see why the greedy algorithm will open all facilities.</strong> I can see how this would be the case if the cost of each element in set <span class="math-container">$S_i$</span> is <span class="math-container">$\sum\limits_{j=1}^ip^{j-1}$</span>, but in this case opening one facility will have cost <span class="math-container">$$p^k + \sum_{i=1}^{k-1}p^{k-i+1}\sum_{j=1}^ip^{j-1} = \Theta(kp^k),$$</span> while they claim that the optimal cost (that of opening one facility) is <span class="math-container">$$p^k + \sum_{i=1}^{k-1}\sum_{j=1}^ip^{j-1} = \Theta(p^k).$$</span> A central part of their proof seems to be that since the greedy algorithm described above will open all <span class="math-container">$k$</span> facilities, it will have cost <span class="math-container">$\Omega(kp^k)$</span> and therefore, the gap between the algorithms performance and the optimum is <span class="math-container">$\Omega(k)$</span>. Since there are <span class="math-container">$n = \Theta(p^k)$</span> clients, <span class="math-container">$k = \log_p n = \ln n/\ln p$</span>, and therefore for <span class="math-container">$p = \ln n$</span>, we have that the gap is <span class="math-container">$\Omega\left(\frac{\log n}{\log \log n}\right)$</span>. </p> <p><strong>Another question I have is that for <span class="math-container">$p = O(1)$</span>, wouldn't this result in a gap of <span class="math-container">$\Omega(\log n)$</span> which is a stronger result? Why doesn't this work?</strong> The last sentence of their paragraph is "We do not know whether the approximation factor of Hochbaum’s algorithm on metric instances is strictly less than <span class="math-container">$\log n$</span>." So I assume I'm missing something.</p> <hr> <p><sub> Reference </sub></p> <p><sub>  Jain, K., Mahdian, M., Markakis, E. <em>et al.</em> (2003). Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing LP. <em>Journal of the ACM.</em> <strong>50(6)</strong>:795–824.</sub></p> https://or.stackexchange.com/q/430 20 Real-world examples of supply chain contracts? LarrySnyder610 https://or.stackexchange.com/users/38 2019-06-13T13:38:51Z 2019-10-18T07:58:53Z <p>Does anyone know of any real-world examples in which supply chain contracts, of the type introduced by <a href="https://doi.org/10.1287/mksc.1070.0336" rel="noreferrer">Pasternack (1985)</a> and reviewed by <a href="https://doi.org/10.1016/S0927-0507(03)11006-7" rel="noreferrer">Cachon (2003)</a>, are actually used in practice? I'm talking about contracts formulated as Stackelberg games, with a transfer payment between the two players, and expected profit functions that are optimized to find the Nash equilibrium for both players. </p> <p>The only such case study that I know of is <a href="https://doi.org/10.1287/inte.33.6.18.25187" rel="noreferrer">this Interfaces article</a> about McGriff tire treading company. But I'm curious to find out about either other published case studies or anecdotal knowledge.</p> https://or.stackexchange.com/q/339 10 Units in the EOQ problem LarrySnyder610 https://or.stackexchange.com/users/38 2019-06-10T01:19:30Z 2019-10-20T13:15:19Z <p>This is a very basic question about a very basic model, but I can't come up with a satisfactory answer.</p> <p>In the economic order quantity (EOQ) model, let <span class="math-container">$\lambda$</span> be the demand rate (<strong>items/year</strong>), <span class="math-container">$h$</span> be the holding cost (<strong>\$/item/year</strong>), and let <span class="math-container">$K$</span> be the fixed cost per order. The optimal solution is <span class="math-container">$$Q^* = \sqrt{\frac{2K\lambda}{h}}.$$</span></p> <p><strong>What should be the units for <span class="math-container">$K$</span>?</strong> One option is just <strong>\$</strong>, which would give <span class="math-container">$Q^*$</span> units of <span class="math-container">$$\sqrt{\frac{\ \cdot \frac{\text{item}}{\text{year}}}{\frac{\}{\text{item}\cdot\text{year}}}} = \text{item},$$</span> which is right.</p> <p>But it seems equally plausible to me to use <strong>\$/order</strong> as the units for <span class="math-container">$K$</span>, but then we have units <span class="math-container">$$\sqrt{\frac{\frac{\}{\text{order}} \cdot \frac{\text{item}}{\text{year}}}{\frac{\}{\text{item}\cdot\text{year}}}} = \text{item}\sqrt{\frac{1}{\text{order}}},$$</span> which obviously doesn't make sense. It would also work out if there were another <span class="math-container">$\sqrt{1/\text{order}}$</span> somewhere, so that <span class="math-container">$Q^*$</span> has units <span class="math-container">$\text{item}/\text{order}$</span>, but none of the other terms should have <span class="math-container">$\text{order}\$</span> in their units.</p> <p>What am I missing? </p> https://or.stackexchange.com/q/12 25 Stochastic programming MIP solvers Albert Schrotenboer https://or.stackexchange.com/users/48 2019-05-30T22:41:08Z 2019-10-16T14:48:08Z <p>I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work with programming environment ? </p>