Recent Questions - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2023-10-01T23:08:45Z https://or.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/11062 0 how to linearize if-then when having an operand? Hemfri https://or.stackexchange.com/users/11802 2023-10-01T22:10:02Z 2023-10-01T22:27:13Z <p>if <span class="math-container">$x_{i,j,p,s}$</span> and <span class="math-container">$y_{i,j,p,s}$</span> are binary and <span class="math-container">$z_i^s$</span> is integer; how to enforce:</p> <p><span class="math-container">$$((x_{i,j,p,s}=1) \land (z_i^s \ge 5 )) \implies y_{i,j,p,s}=1$$</span></p> <p>The value of <span class="math-container">$z$</span> in my problem could be 1 to maximum of 10.</p> https://or.stackexchange.com/q/11059 0 Relaxing non-affine equality constraints in convex optimization mhdadk https://or.stackexchange.com/users/7263 2023-10-01T20:40:56Z 2023-10-01T22:40:33Z <p>Consider the convex function <span class="math-container">$f$</span>. In section 4.2.1 in <a href="https://www.stat.cmu.edu/%7Eryantibs/convexopt-F18/scribes/Lecture_4.pdf" rel="nofollow noreferrer">these lecture notes</a>, the author writes:</p> <blockquote> <h3>4.2.1 Relaxing non-affine equality constraints</h3> <p>For functions <span class="math-container">$g_i(x)$</span>, <span class="math-container">$i \in \{1,\dots,d\}$</span> that are convex but not affine, we relax <span class="math-container">\begin{equation} \begin{aligned} \min \quad &amp; f(x), \\ \textrm{s.t.} \quad &amp; {\color{blue}{g_i(x) = 0, \ i \in \{1,\dots,d\}}} \\ \quad &amp; Ax = b \\ \quad &amp; h_i(x) \leq 0 \end{aligned} \implies_{\!\!\!\text{relax}} \begin{aligned} \min \quad &amp; f(x), \\ \textrm{s.t.} \quad &amp; {\color{blue}{g_i(x) \leq 0, \ i \in \{1,\dots,d\}}} \\ \quad &amp; Ax = b \\ \quad &amp; h_i(x) \leq 0 \end{aligned} \end{equation}</span> as the original formulation is a non-convex problem (non-affine equalities are not convex). The relaxed formulation turns affine equalities into affine <em>inequalities</em>, so thus has more feasible points and is now convex.</p> </blockquote> <p>I'm not sure why the author converted the constraint &quot;<span class="math-container">$g_i(x) = 0, \ i \in \{1,\dots,d\}$</span>&quot; to &quot;<span class="math-container">$g_i(x) \leq 0, \ i \in \{1,\dots,d\}$</span>&quot; rather than &quot;<span class="math-container">$g_i(x) \geq 0, \ i \in \{1,\dots,d\}$</span>&quot;, since both kinds of relaxations have the original constraint <span class="math-container">$g_i(x) = 0$</span> as a subset. One reason would be that the constraint <span class="math-container">$g_i(x) \leq 0$</span> is a convex subset of the epigraph of the convex functions <span class="math-container">$g_i(x)$</span>. Therefore, <span class="math-container">$g_i(x) \leq 0$</span> defines a convex set, while <span class="math-container">$g_i(x) \geq 0$</span> may not. However, I'm not sure if this reasoning is correct.</p> https://or.stackexchange.com/q/11056 0 How can I handle a constraint on a terminal state variable while avoiding infeasibility during SDDP.jl training process? Engr. Moiz Ahmad https://or.stackexchange.com/users/10727 2023-09-30T15:56:22Z 2023-10-01T00:13:52Z <p>I want to solve a multi-stage optimization problem using SDDP.jl in which I am having hard time using constraints on state variables at the termination.</p> https://or.stackexchange.com/q/11053 1 Metaheuristics must read articles and new research fields Josa Ferreira https://or.stackexchange.com/users/2900 2023-09-30T01:51:57Z 2023-09-30T15:45:10Z <p>Where can I find the fundamentals and the must read articles on metaheuristics? Additionally, what are the current research focal points and areas of interest in this field?</p> <p>I'm dedicated to gaining a comprehensive understanding of the subject and have been exploring resources such as Wikipedia (<a href="https://en.wikipedia.org/wiki/Metaheuristic#Contributions" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Metaheuristic#Contributions</a>) and scholarly papers authored by renowned researchers on Google Scholar (<a href="https://scholar.google.com/citations?hl=en&amp;view_op=search_authors&amp;mauthors=label%3Ametaheuristics&amp;btnG=" rel="nofollow noreferrer">https://scholar.google.com/citations?hl=en&amp;view_op=search_authors&amp;mauthors=label%3Ametaheuristics&amp;btnG=</a>). But I would also like to know from researchers from here.</p> https://or.stackexchange.com/q/11051 1 Is this classed as a version of jobshop? How should it be approached? Faolian https://or.stackexchange.com/users/12550 2023-09-29T10:48:35Z 2023-09-29T20:40:33Z <p>I'm looking at a problem that seems quite like flexible jobshop, but as I understand it jobshop is basically all about finding the order/sequence of tasks (across multiple machines potentially), however as far as I can tell it doesn't consider times. The problem I'm looking at has some jobs that will only be available to start at a specific time (earliest start time) and also may have their own deadlines for completion.</p> <p>I could approach this just by setting constraints on those tasks not starting until t&gt;earliest start time, but it seems like that would be potentially limiting?</p> <p>Can anyone point me to what this may be called if its not a version of jobshop, or if it is jobshop how to best approach the differences?</p> https://or.stackexchange.com/q/11046 2 How to define the sequence depending setup time based on a time index formulation A.Omidi https://or.stackexchange.com/users/199 2023-09-27T12:36:55Z 2023-09-28T13:15:46Z <p>I am working on a scheduling problem in which I have used two different MIP formulations and also based on the time index variable. My problem is in the class <span class="math-container">$P_{j} | \ r_{j}, SDST \ | C_{Max}$</span>.</p> <p>Without having <span class="math-container">$SDST$</span>, both formulations work well, but it makes an issue when I want to add the related constraints. Actually, the problem is solved, but the resulting schedule does not make sense against the <span class="math-container">$SDST$</span> limitation. The constraint I have used is in the following form:</p> <p><span class="math-container">$$\sum_{i_{i\neq j}} \sum_{tt=t+p_{j}}^{t+p_{j}-s_{j,i}-1} x_{i,m,tt} \leq M.(1-x_{j,m,t}) \quad \forall j \in J, m \in M, t \in T$$</span></p> <p>where the binary variable <span class="math-container">$x_{j,m,t}$</span> is equal to <span class="math-container">$1$</span> if task <span class="math-container">$j$</span> is being assigned on machine <span class="math-container">$m$</span> at time slot <span class="math-container">$t$</span>, otherwise <span class="math-container">$0$</span>. I was wondering if, how can I fix my issue w.r.t the mentioned constraint and if there is another efficient way to do that.</p> https://or.stackexchange.com/q/11045 1 Matrix lookup modelling variants Christian https://or.stackexchange.com/users/9644 2023-09-27T07:22:10Z 2023-09-27T15:57:04Z <p>As part of a bigger model I have a matrix of variables <span class="math-container">$x_{ij} \geq 0$</span> and a &quot;selector&quot; set of variables <span class="math-container">$y_j \in \{0,1\}, \sum_j y_j = 1$</span>. From <span class="math-container">$x_{ij}$</span> I'd like to get the variables of column <span class="math-container">$j$</span>, where <span class="math-container">$y_j = 1$</span>, so it's kind of a matrix lookup: <span class="math-container">$x_{.j}$</span> with <span class="math-container">$j = \sum_k k \space y_k$</span></p> <p>I'm interested in efficient modelling variants to achieve this. Probably there is not <em>the</em> best variant, as it largely depends on the other parts of the model, so proposals are welcomed.</p> <p>My approach:</p> <p><span class="math-container">$c_i$</span>: columns of <span class="math-container">$x_{ij}$</span> where <span class="math-container">$y_j = 1$</span> <span class="math-container">$$\forall i: c_i = \sum_j x_{ij} \space y_j$$</span> As <span class="math-container">$x_{ij} \space y_j$</span> is not linear, I introduce substitute <span class="math-container">$z_{ij} \geq 0$</span> and <span class="math-container">$M$</span> as upper bound on <span class="math-container">$x_{ij}$</span> with</p> <p><span class="math-container">$$0 \leq z_{ij} \leq x_{ij} \\ x_{ij} - M (1 - y_j) \leq z_{ij} \leq M \space y_j \\$$</span> So <span class="math-container">$c_i = \sum_j z_{ij}$</span> with the constraints from above. It works, but I wonder if it can be improved. What I don't like (beside Big-M) is that I have to introduce additional variables in the size of <span class="math-container">$x_{ij}$</span> plus 3 additional constraints per variable - and in the end I only need <span class="math-container">$c_i$</span>. The <span class="math-container">$z_{ij}$</span> are just &quot;intermediates&quot;.</p> https://or.stackexchange.com/q/11042 0 How to identify constraints that make problem not solvable in polynomial time? somewhere https://or.stackexchange.com/users/12372 2023-09-27T00:54:19Z 2023-09-27T03:56:17Z <p>I am reading <a href="https://arxiv.org/pdf/1910.13045.pdf" rel="nofollow noreferrer">this paper</a>, available for free viewing, which contains an example of job shop scheduling, shown below.</p> <p><a href="https://i.stack.imgur.com/nEdf1.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/nEdf1.png" alt="part_1" /></a> <a href="https://i.stack.imgur.com/dROqr.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dROqr.png" alt="part_2" /></a></p> <p>The details of the variable definitions, etc., can be found in the paper, but it's a pretty typical job scheduling problem. The paper solves it by decomposing it into an MILP and a Constraint Programming sub-problem. The MILP part is supposed to be &quot;easy to solve&quot; in some sense (i.e. polynomial time).</p> <p>What I don't understand is: why is the MILP they have identified is any easier to solve than the original problem? Is it because constraints (13) and (16) involve more than one binary variable? To me, constraint (12) seems very difficult to satisfy, but for some reason that is included in the MILP. Faced with a general MILP, how to identify constraints which are more difficult to satisfy?</p> https://or.stackexchange.com/q/11035 2 OR-Tools CP-SAT solver: is it possible to name a constraint like in GUROBI Issouf https://or.stackexchange.com/users/9755 2023-09-25T17:25:50Z 2023-09-25T18:36:38Z <p>I try to implement cp model with OR-tools CP-SAT solver. Please, is it possible to name constraints for being able to manage conflict later like for variables: <code>t_var[i] = model.NewBoolVar(f&quot;affect_{i}&quot;)</code></p> https://or.stackexchange.com/q/11032 -1 mip - mapping of equality to boolean variable gregy4 https://or.stackexchange.com/users/4412 2023-09-25T15:21:27Z 2023-09-25T17:58:51Z <p>I want to create mip model which assign workers to entities. In case neighbour entities use same worker, objective should be increased by 1. A goal is to maximize total number of same workers for neighbour entities.</p> <p>Since number of combinations can be large, I prefer integer variable to hold index of assigned worker (allowed only one worker per entity) to an entity. It works for me with usage of big M, boolean variable (assignment of concrete worker) is mapped to an index.</p> <p>I don't how to map equality of indexes for two entities to boolean variable.</p> <p>For example</p> <ul> <li>e1.w = 1, e2.w = 1 imply 1</li> <li>e1.w = 2, e2.w = 1 imply 0</li> <li>e1.w = 2, e2.w = 2 imply 1</li> </ul> <p>Is it possible to model it in mip ? Otherwise I have to for every possible combination of indexes create less or equal equation to trigger equality of workers.</p> https://or.stackexchange.com/q/11031 1 How to properly tackle a big model using weak constraints Marco https://or.stackexchange.com/users/12523 2023-09-25T15:01:29Z 2023-09-25T21:52:57Z <p>I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is.</p> <p>One suggestion I got is to use lazy constraints in order to limit the number of constraints, so that the model can be lighter, but I'm not sure I understand how they should be used.</p> <p>Lazy constraints are constraints that get checked against a solution that satisfies all normal constraints, and in case they get violated, they get added as new constraints.</p> <p>The problem with my model is that it can generate many solutions that have the same score, so I fear that a very large number of solutions would have to be tested against these lazy constraints, which they'd violate, resulting in many iterations of this process, and in each of these iterations many violations would be found (meaning that a very large number of constraints would be added anyway).</p> <p>So, how do I use lazy constraints? Do I set as lazy only the constraints that rarely get violated, while keeping the others as normal? Or should I make a weak model, strenghtening it with lazy constraints?</p> https://or.stackexchange.com/q/11030 0 At the start of the execution of SDDP.jl, when there is no value approximation & terminal states available, what cost-to-go estimation is used? Engr. Moiz Ahmad https://or.stackexchange.com/users/10727 2023-09-25T10:07:40Z 2023-09-25T19:06:19Z <p>I am using SDDP.jl for my research and want to know that at the very start of the execution, when there is no value function initialization and terminal state (for backward recursion), how cost-to-go function is initialized?</p> <p>In other words, what cost-to-go function is optimized at the very first forward pass in SDDP.jl implementation.</p> https://or.stackexchange.com/q/11029 0 different constraints for each row Angel Diaz https://or.stackexchange.com/users/12522 2023-09-25T09:45:29Z 2023-09-27T09:01:57Z <p>I'm using the IpSolve package to solve a problem to optimize the assignment (minimum distance) between sellers (rows)and customers (columns) using Rstudio.</p> <p>The problem I faced when using lp/lp.transport is that I don't know how to introduce different constraints for each row. For example I want to establish that the sellers have between a minimum and a maximum number of customers, but as far as I know, I only can establish one constraint for each row.</p> <p>Do you know how I can solve this ??</p> <p>Do you know another more efficient way of solving this kind of problems when huge data is analyzed?</p> https://or.stackexchange.com/q/11028 1 How does one model weather in Simio and have it change how vehicles operate within the model? Miss Mae https://or.stackexchange.com/users/10807 2023-09-25T06:52:58Z 2023-09-29T09:02:15Z <p>For context, I am using the Simio modeling software for an OR class, and for fun I am making a simulation model of the traffic outside my dorm. I have recreated the layout and distance of the streets, and I plan on taking the stats for an hour a day for two weeks on how many cars arrive at what time, how long they wait, etc. Simply put, I'm curious about playing around and seeing various traffic behaviors that arise while modeling.</p> <p>However, it rains often where I am at, say for any given day there's a 10% it will rain (for 12 hours a day) with the following occurrences (given the speed limit for these roads is 20mph):</p> <ul> <li><p>50% chance a car will slow down from 1~5mph (randomly) to caution the wet roads</p> </li> <li><p>50% chance will not slow down and will go the full 20mph</p> </li> </ul> <p>Ultimately, I want to model the weather and have it change how vehicles operate within the model. I am however quite newbish with Simio and am going above my own scope of what is required for this class, and every resource I try to find online about this doesn't have anything that can answer or assist with this</p> <p>The first thing I investigated was some sort of trigger that would have a 10% chance to activate per day, and have that trigger alter the vehicle's desired speeds, but then I'm unsure how this would handle the case of cars that will go the 20mph regardless, or the cars that have speeds anywhere between 15~20mph (in other words, handle when vehicles are spawned whether or not they will have varying altered speeds and how this would be timed for when it will stop raining in the 12hr mark)</p> https://or.stackexchange.com/q/11027 -2 Optimize Packaging Dimension overboxed https://or.stackexchange.com/users/10000 2023-09-24T09:29:26Z 2023-09-24T19:02:36Z <p>I want to optimize the transport packaging (which is in carton/box) in logistics activity. The key question in this case is what is the optimal dimension of the carton, as the number of cartons carried in a truck container is maximized. Is there any reference or model for this type of problem?</p> https://or.stackexchange.com/q/11026 0 Handling Variable Division in CVXPY for Calculating Annualized Rate of Change user760900 https://or.stackexchange.com/users/12516 2023-09-24T07:23:30Z 2023-09-24T07:23:30Z <p>I am working with a dataset that contains multiple entries for different IDs across various years. Some IDs might have a gap of years between entries. My goal is to solve an optimization problem using CVXPY, where I impose constraints based on the annualized rate of change of a variable associated with each ID across years. When there are gaps between years for a given ID, I aim to consider the rate of change as evenly distributed across the gap years. For instance, if an ID has a 20% increase from the year 2010 to 2012, I calculate the annualized rate of change as <span class="math-container">$\sqrt[2012-2010]{\frac{{\text{value2012}}}{\text{value2010}}}$</span></p> <p>However, when incorporating this logic into my CVXPY problem, I am encountering a <code>DCPError: &quot;Problem does not follow DCP rules&quot;</code>.</p> <p>Below is a simplified version of my code that illustrates the issue:</p> <pre class="lang-py prettyprint-override"><code>import cvxpy as cp # Define CVXPY variables vars = { &quot;value2010&quot;: cp.Variable(name=&quot;value2010&quot;), &quot;value2012&quot;: cp.Variable(name=&quot;value2012&quot;), } # Initialize constraints list constraints = [] gap_years = 2012 - 2010 c = cp.Variable(nonneg=True) # Calculate the annualized deviation and add the constraint annualized_deviation = cp.power(vars[&quot;value2012&quot;] / vars[&quot;value2010&quot;], 1/gap_years) constraints.append(cp.square(annualized_deviation - 1) &lt;= c) # Additional constraints/data for value2010/value2012 would be added here # Define the objective function and solve the problem objective = cp.Minimize(c) problem = cp.Problem(objective, constraints) problem.solve() </code></pre> <p>I understand that the error arises due to the division of one CVXPY variable by another, as discussed in several posts (<a href="https://or.stackexchange.com/questions/8455">1</a>, <a href="https://stackoverflow.com/questions/74491368">2</a>, <a href="https://stackoverflow.com/questions/69973713">3</a>, <a href="https://stackoverflow.com/questions/69973713">4</a>, <a href="https://stackoverflow.com/questions/56589885">5</a>). I have also read <a href="https://or.stackexchange.com/a/5041/12516">this answer</a> that raises the possibility of variable division under certain conditions by converting the problem to QCP, but I am not entirely sure how to apply this to my specific case.</p> <p>I would appreciate any guidance on how to address this issue, whether through an alternative formulation, clarification of the concepts involved, or any other means to incorporate the annualized rate of change in a optimization problem while handling year gaps.</p> https://or.stackexchange.com/q/11025 0 In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint? IsalanOnkar https://or.stackexchange.com/users/12208 2023-09-23T19:08:04Z 2023-09-26T06:58:46Z <p>In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an <em>elementary</em> path, meaning that no vertices are repeated.</p> <p>However, when an elementary path is NOT required, then it is fairly common to include a constraint that ensures there are no <em>subtours</em> meaning that there are no isolated tours that do not start at, and return to, the specified depot.</p> <p>From my understanding, it would never be necessary to include both of these constraints. However, in some cases I have seen both of these constraints, for example here: <a href="https://par.nsf.gov/servlets/purl/10074741" rel="nofollow noreferrer">https://par.nsf.gov/servlets/purl/10074741</a></p> <p><a href="https://i.stack.imgur.com/8Aqca.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8Aqca.png" alt="Problem Description" /></a> <a href="https://i.stack.imgur.com/4J2Zs.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4J2Zs.png" alt="MILP" /></a> In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?</p> <p><strong>EDIT</strong> I've found another resource which highlights my intuition: In <a href="https://backend.orbit.dtu.dk/ws/portalfiles/portal/5065984/BK_PhD_thesis_final_060110.pdf" rel="nofollow noreferrer">this book</a> it describes a similar problem, the vehicle routing problem with time windows. And, in its MILP formulation (shown below), it does not have subtour elimination constraints, and explicitly mentions <em>the classical VRP subtour elimination constraints become redundant</em>. Now, I would have expected this to be the same reason why the image <a href="https://i.stack.imgur.com/4J2Zs.png" rel="nofollow noreferrer">2</a> would not need the subtour elimination constraints, since in both cases, the direction of traversal is indicated by denoting <span class="math-container">$(i,j)$</span>.</p> <p><a href="https://i.stack.imgur.com/6zDE1.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/6zDE1.png" alt="MILP_VRPTW" /></a> <a href="https://i.stack.imgur.com/GVb4D.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GVb4D.png" alt="subtour_redundant" /></a></p> <p>The difference between these two MILP formulations and problem statements might help me understand what you guys are getting at. Is the only difference that one of them imposes a unique direction?</p> https://or.stackexchange.com/q/11024 1 Optimize cherry picking runs Ryan https://or.stackexchange.com/users/12513 2023-09-23T18:11:31Z 2023-09-23T18:11:31Z <p>I am trying to optimize a cherry picking procedure on 96-well <a href="https://en.m.wikipedia.org/wiki/Microplate" rel="nofollow noreferrer">microplates</a>. The plates are 12X8 (12 columns, 8 rows). We pass a command file that has many lines like this to a robot:</p> <pre><code>source_plate, source_well, destination_plate, destination_well </code></pre> <p>The robot has an arm that can cherry pick 8 positions at a time. The 8 source positions can be anywhere on any source plate, but the 8 corresponding destination positions should always be a complete or mostly complete column. This way the robot can dispense material to the destination plates in one action rather than 8 separate actions.</p> <p>For a given run, the robot can hold a maximum of 30 96-well microplates and the loaded command file should contain only source and destination plates that are actually on the robot's deck. Let's assume the following constraints:</p> <ul> <li>1500 total raw command lines (i.e. I want to cherry pick 1500 positions)</li> <li>130 source plates</li> <li>30 destination plates</li> </ul> <p>Given the 30-plate-maximum-per-run constraint, I'm trying to a find way to break those 1500 raw command lines into runs (i.e. command files) such that the number of times plates have to swapped on/off the deck is minimized. The difference between an optimized vs a naive approach could be one day or more of work in this case.</p> <p>I'm struggling to formulate the above scenario in terms of an objective function in which plate swapping events are minimized between runs. Also I'm unsure of the most appropriate method to use (e.g. linear programming, etc.) Any help would be appreciated</p> https://or.stackexchange.com/q/11021 1 How to linearize stepped pricing in a route assignment problem Ying https://or.stackexchange.com/users/12326 2023-09-23T15:37:07Z 2023-09-24T03:24:29Z <p>There is an allocation problem, while we have to assign logistics routes to multiple candidate carriers.</p> <p>For simplicity, let's assume there are only two routes, <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, with two candidate carriers, <span class="math-container">$P$</span> and <span class="math-container">$Q$</span>. The total number of orders for route <span class="math-container">$A$</span> is <span class="math-container">$N_a$</span> and for route <span class="math-container">$B$</span> is <span class="math-container">$N_b$</span>. Carrier <span class="math-container">$P$</span> provides unit prices <span class="math-container">$P_a$</span> and <span class="math-container">$P_b$</span> for routes <span class="math-container">$A$</span> and <span class="math-container">$B$</span> respectively, while carrier <span class="math-container">$Q$</span> provides unit prices <span class="math-container">$Q_a$</span> and <span class="math-container">$Q_b$</span> for routes <span class="math-container">$A$</span> and <span class="math-container">$B$</span> respectively. Both carrier <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> also provide stepped pricing types based on the number of orders they undertake (i.e., order quantity step), with two steps assumed for simplicity.</p> <p>For carrier <span class="math-container">$P$</span>, the discount coefficient for the total freight cost is <span class="math-container">$c_1$</span> when the number of orders is between <span class="math-container">$[0, M_1)$</span>, and <span class="math-container">$c_2$</span> when the number of orders is <span class="math-container">$[M_1, inf)$</span>. The problem is how to allocate the orders for these two routes to the two carriers, <span class="math-container">$P$</span> and <span class="math-container">$Q$</span>, in such a way as to minimize the total cost of the freight.</p> <hr /> <p>For example, let's say the total order volumes for routes <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are <span class="math-container">$N_a = 100$</span> and <span class="math-container">$N_b = 200$</span>, respectively, with unit prices of <span class="math-container">$P_a = 2$</span> and <span class="math-container">$P_b = 3$</span>, and unit prices of <span class="math-container">$Q_a = 3$</span> and <span class="math-container">$Q_b = 2$</span>. The step details are <span class="math-container">$M_1 = 120$</span>, <span class="math-container">$c_1 = 0.8$</span>, and <span class="math-container">$c_2 = 0.6$</span>.</p> <p>Assuming that carrier <span class="math-container">$P$</span> is assigned 60 orders for route <span class="math-container">$A$</span> and 80 orders for route <span class="math-container">$B$</span>, while carrier <span class="math-container">$Q$</span> is assigned the remaining orders, i.e., 40 orders for <span class="math-container">$A$</span> and 120 orders for <span class="math-container">$B$</span>, the total cost (without discount) for carrier <span class="math-container">$P$</span> is calculated as 60 * 2 + 80 * 3 = 360. The total shipment volume is 60 + 80 = 140, which falls in the second step, with a discount factor of 0.6. Therefore, the total freight charge payable to carrier P is 360 * 0.6.</p> <p>Similar calculations can be made for carrier <span class="math-container">$Q$</span>.</p> <hr /> <p>To formulate this problem, let <span class="math-container">$I$</span> be the set of routes and <span class="math-container">$J$</span> be the set of carriers. The decision variable <span class="math-container">$x_{ij}$</span> represents the quantity of orders assigned from route <span class="math-container">$i$</span> to carrier <span class="math-container">$j$</span>.</p> <p>The first constraints is <span class="math-container">$\sum\limits_{j}{x_{ij}} = N_i$</span>.</p> <p>Then we introduce a binary variable <span class="math-container">$\mu_{kj}$</span> to indicates whether the total number of orders assigned to carrier <span class="math-container">$j$</span> follows into the <span class="math-container">$k$</span>th interval, thus we have <span class="math-container">$\sum\limits_{k}{\mu_{kj}} = 1,\forall j$</span>.</p> <p>Then the continuous variable <span class="math-container">$\pi_{kj}$</span> to indicate the actual number of orders in interval <span class="math-container">$k$</span>, thus we have <span class="math-container">$M_{k-1,j}\mu_{kj} \leq \pi_{kj} \leq M_{kj} \mu_{kj}$</span></p> <p>The second constraint is <span class="math-container">$\sum\limits_{i}{x_{ij}} = \sum\limits_{k}{\pi_{kj}},\forall j$</span>, which represent the number of orders undertake by each carrier <span class="math-container">$j$</span>.</p> <p>The total freights of carrier <span class="math-container">$j$</span> is <span class="math-container">$\sum\limits_{i}{p_i x_{ij}}$</span> multiplied by <span class="math-container">$c_{kj}$</span>, which indicated by <span class="math-container">$\mu_{kj}$</span>, will introduce the nonlinearity.</p> https://or.stackexchange.com/q/11020 1 How to cmpute IIS using the Or-Tools solver? Ying https://or.stackexchange.com/users/12326 2023-09-23T11:15:22Z 2023-09-23T11:37:12Z <p>I'm trying to solve a MIP using Google Or-Tools, but it's showing that the model is <em><strong>infeasible</strong></em>. I'd like to know if there is a convenient way to analyze which constraint or variable bounds are causing the infeasibility of the model. I want to use the built-in methods of Or-Tools only, without using any third-party packages.</p> <blockquote> <p>presolving:</p> <p>presolving (1 rounds: 1 fast, 0 medium, 0 exhaustive):</p> <p>11 deleted vars, 8 deleted constraints, 0 added constraints, 6 tightened bounds, 0 added holes, 1 changed sides, 0 changed coefficients</p> <p>0 implications, 0 cliques</p> <p>presolving detected infeasibility</p> <p>Presolving Time: 0.00</p> <p>SCIP Status : problem is solved [infeasible]</p> <p>Solving Time (sec) : 0.00</p> <p>Solving Nodes : 0</p> <p>Primal Bound : +1.00000000000000e+20 (0 solutions)</p> <p>Dual Bound : +1.00000000000000e+20</p> <p>Gap : 0.00 %</p> </blockquote> https://or.stackexchange.com/q/11019 1 MOO: Variable is both a decision variable and an objective veeman https://or.stackexchange.com/users/12504 2023-09-22T18:45:33Z 2023-09-22T18:50:45Z <p>I'm trying to solve a Multi-Objective Optimization Problem to find the set of Pareto Optimal Solutions. I have a list of decision variables (x1, x2, x3) and a list of objectives (o1, o2, x3). As you can see, one of the variables is both a decision variable and an objective. Is this a good way to formulate this problem or are there more efficient ways to do it? Also, are you aware of any research that look into problems that have a variable as both a decision variable and objective?</p> https://or.stackexchange.com/q/11018 1 What is the use of solvers that return approximately-feasible solutions? Erel Segal-Halevi https://or.stackexchange.com/users/2576 2023-09-22T09:05:28Z 2023-09-22T09:05:28Z <p>Common methods for solving convex programs return solutions that are only approximately-feasible solutions. Here is an example (from lecture notes by Nemirovski on interior-point methods for convex programming). Consider the following convex program:</p> <p><a href="https://i.stack.imgur.com/nKdLC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/nKdLC.png" alt="enter image description here" /></a></p> <p>Interior point methods return solutions satisfying the following, for any given <span class="math-container">$\epsilon&gt;0$</span>:</p> <p><a href="https://i.stack.imgur.com/7S2Pl.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7S2Pl.png" alt="enter image description here" /></a></p> <p>that is: the constraints represented by the functions <span class="math-container">$g_j$</span> are not satisfied exactly - they are satisfied only approximately (up to <span class="math-container">$\epsilon$</span>).</p> <p>In some cases, approxiamtely-feasible solutions may be possible. For example, if the constraints represent budget, we may be able to get a slightly larger budget than planned. But sometimes it is impossible. For exmaple, if we look for a probability distribution, then the sum of probabilities must be 1 - we cannot have a distribution with sum of probabilities larger than 1.</p> <p>In all papers that use convex programming, I have never seen any mention of this &quot;approximately-feasible&quot; issue. This is quite puzzling: how can we be sure that a solution, that is only approximately-feasible, is useful in practice?</p> https://or.stackexchange.com/q/11016 1 Is it possible to do a linearization without introducing new variables? Rainbow https://or.stackexchange.com/users/11476 2023-09-21T16:43:01Z 2023-09-21T19:12:34Z <p>I have three binary variables <span class="math-container">$x_{i,j}^{m,r}$</span> , <span class="math-container">$y_i^{m,r}$</span>, and <span class="math-container">$z_i^{m,r}$</span>. There is another integer variable <span class="math-container">$w_i^r$</span>. And I want to linearize the following logic:</p> <p><span class="math-container">$$\sum_{m} x_{i,j}^{m,r} \ge 1 \implies w_j^r = w_i^r + \sum_{m} y_j^{m,r} - \sum_{m} z_j^{m,r} \qquad \forall r, i, j$$</span></p> <p>I think to linearize the above I need to introduce another binary. But could we do it without any new variables?</p> https://or.stackexchange.com/q/11014 0 How should one proceed with column generation when the subproblem generates only columns with positive reduced costs? Nada.S https://or.stackexchange.com/users/5537 2023-09-20T12:42:31Z 2023-09-22T12:49:24Z <p>I try to solve a MILP with Column generation. The Master Problem is a minimization problem with &quot; <span class="math-container">$\le$</span> &quot; constraint which lead to non-positive dual values. The problem is that the subproblem returns just columns with positive reduced cost which seems logical because <span class="math-container">$\overline{c_{i j}}=c_{i j}-\pi_{i j}\geq 0$</span>, where <span class="math-container">$c_{i j}=d_{i j} \text{(distance to travel from$i$to$j$)} \geq 0 \forall(i, j)$</span>. The question is how could make progress in Column Generation algorithm in this situation. (N.B: The objective of the Master Problem is to minimize <span class="math-container">$\sum_{r \in \bar{\omega}} c_r y_r$</span>, and the objective of the Subproblem is to minimize <span class="math-container">$\sum_{(i, j) \in r} \overline{c_{i j}} x_{i j}$</span>.)</p> https://or.stackexchange.com/q/10941 3 Can the following problem be cast as a geometric program? mhdadk https://or.stackexchange.com/users/7263 2023-09-06T19:36:48Z 2023-09-20T22:13:55Z <p>Consider the function <span class="math-container">$f : [0,1]^n \to [0,\infty)$</span> defined as <span class="math-container">$$f(x_1,\dots,x_n) = \sum_{(z_1,\dots,z_n) \in \{0,1\}^n} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right]$$</span> where <span class="math-container">$g(z_1,\dots,z_n) \geq 0$</span> for every <span class="math-container">$(z_1,\dots,z_n) \in \{0,1\}^n$</span>. Note that the summation consists of <span class="math-container">$2^n$</span> terms. My objective is to solve the following problem: <span class="math-container">\begin{equation} \begin{aligned} \min_{x_1,\dots,x_n} \quad &amp; f(x_1,\dots,x_n), \\ \textrm{s.t.} \quad &amp; (x_1,\dots,x_n) \in \{y \in \mathbb R^n \mid y_1 \in [a_{1},1],\dots,y_n \in [a_{n},1]\} \end{aligned} \tag{1} \label{prob} \end{equation}</span> where <span class="math-container">$0 \leq a_i &lt; 1$</span> for each <span class="math-container">$i$</span>. In other words, the decision variables <span class="math-container">$x_1,\dots,x_n$</span> are constrained to be within an <span class="math-container">$n$</span>-dimensional hyperrectangle that is a subset of an <span class="math-container">$n$</span>-dimensional hypercube. To solve the problem in \eqref{prob}, my strategy was to convert it into the standard form for a geometric program and then pass it to a solver. However, the main difficulty in doing so is that the literature that I have found on geometric programming constrain <span class="math-container">$g(z_1,\dots,z_n)$</span> to be strictly positive for every <span class="math-container">$(z_1,\dots,z_n) \in \{0,1\}^n$</span>, while in my case, it can be <span class="math-container">$0$</span> for some <span class="math-container">$(z_1,\dots,z_n) \in \{0,1\}^n$</span>. Therefore, <span class="math-container">$f$</span> is not strictly a posynomial. Any suggestions on how to proceed?</p> <hr /> <p><strong>Update</strong></p> <p>Based on the definitions given <a href="https://inst.eecs.berkeley.edu/%7Eee127/sp21/livebook/l_gp_posy.html" rel="nofollow noreferrer">here</a>, it seems that this isn't really a problem, as the summation in <span class="math-container">$f$</span> can be split as <span class="math-container">\begin{align} f(x_1,\dots,x_n) &amp;= \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) \neq 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \\ &amp;+ \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) = 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \\ &amp;= \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) \neq 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \end{align}</span> However, I wonder if there is a better way to approach this problem in the first place, so I'm keeping this question open.</p> https://or.stackexchange.com/q/10906 0 How to minimize number of machines required to serve tasks, and return the schedules for each machine? underdog987 https://or.stackexchange.com/users/12368 2023-08-30T04:02:52Z 2023-09-30T08:04:00Z <p>The problem I'm trying to solve is the following:</p> <ul> <li>Given <span class="math-container">$t\in \{1,2,3....T\}$</span> tasks, integer.</li> <li>Tasks have release times <span class="math-container">$r_t$</span> and deadlines <span class="math-container">$d_t$</span>, and processing times <span class="math-container">$p_t$</span>, all continuous, real-valued.</li> <li>Minimize the number of machines required to process the tasks, assuming all machines are identical, and pre-emption is not allowed, and machines can only process one job at a time.</li> <li>Also, the schedule itself should be returned - not just the minimum number of machines.</li> </ul> <p>What would be an equivalent MIP or MILP for this problem?</p> <p>I've seen a <a href="https://or.stackexchange.com/questions/9964/">similar question</a> however, their problem is much more simple for two reasons:</p> <ol> <li>The schedule need not be returned</li> <li>Time is discrete.</li> </ol> <p><em>EDIT</em>: If it makes the problem easier, I'm okay with a solution that has discrete time intervals, but it's not clear to me whether that makes the MILP formulation easier or more difficult.</p> https://or.stackexchange.com/q/10901 1 In a routing and scheduling problem with break consideration, How can I determine whether a node is met before a break or after it? Hani Jamshidian https://or.stackexchange.com/users/12362 2023-08-29T10:12:10Z 2023-09-28T18:02:40Z <p>I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some conditions). For some reason, I need to determine whether a visit occurs before or after a break. I defined two binary variables: <span class="math-container">$Z(i,k,t)$</span> which means if patient i is visited by doctor k on shift t <strong>before</strong> the break, and <span class="math-container">$Z'(i,k,t)$</span> for <strong>after</strong> the break. I added 2 new constraints as follows:</p> <p><span class="math-container">$S(b,k,t)-S(i,k,t) =l= M* Z(i,k,t)$</span></p> <p><span class="math-container">$Z(i,k,t) + Z'(i,k,t) =l= \sum_j X(i,j,k,t)$</span></p> <p><span class="math-container">$S(b,k,t)$</span> is the starting time of break by doctor k on shift t</p> <p><span class="math-container">$S(i,k,t)$</span> is the starting time of visiting patient i by doctor k on shift t</p> <p><span class="math-container">$X(i,j,k,t)$</span> is if doctor k on shift t goes from node i to node j (binary variable)</p> <p>In the first constraint, if the left-hand side becomes positive, <span class="math-container">$Z(i,k,t)$</span> will be 1. The second one is guaranteeing that Z and Z' could get value if patient i was visited by doctor k on shift t. By adding these 2 constraints to my model, the result of my S variables (starting time) get wrong. I think it's better to rewrite the first constraint so that it becomes related somehow to <span class="math-container">$X(i,j,k,t)$</span>, but I can not figure out how to do it.</p> https://or.stackexchange.com/q/10866 0 Gurobi founds optimal solution but it is not feasible Franco https://or.stackexchange.com/users/12334 2023-08-23T13:53:34Z 2023-09-24T14:01:50Z <p>I'm currently solving a MIP model with pyomo using gurobi and I am facing strange results.</p> <p>I have one constraint that looks like this:</p> <pre><code>def satisfacer_servicios_r1(modelo, s): return (sum(modelo.x[bv, s] for bv in modelo.BV) == 1) modelo.satisfacer_servicios_r1 = pyo.Constraint(modelo.S, rule=satisfacer_servicios_r1) </code></pre> <p>And x is defined as:</p> <pre><code>modelo.x = pyo.Var(modelo.BV, modelo.S, domain=pyo.Binary) </code></pre> <p>In the solution found by gurobi all x are equal to -1 nonetheless it says that constraint &quot;satisfacer_servicios_r1&quot; is active.</p> <p>Code to check x values:</p> <pre><code>modelo.x.pprint() x : Size=4250, Index=x_index Key : Lower : Value : Upper : Fixed : Stale : Domain (1, 1) : 0 : -0.0 : 1 : False : False : Binary (1, 5) : 0 : -0.0 : 1 : False : False : Binary (1, 11) : 0 : -0.0 : 1 : False : False : Binary (1, 15) : 0 : -0.0 : 1 : False : False : Binary (1, 18) : 0 : -0.0 : 1 : False : False : Binary (1, 31) : 0 : -0.0 : 1 : False : False : Binary (1, 34) : 0 : -0.0 : 1 : False : False : Binary </code></pre> <p>Code to check constraint status:</p> <pre><code>modelo.satisfacer_servicios_r1.pprint() satisfacer_servicios_r1 : Size=85, Index=S, Active=True Key : Lower : Body : Upper : Active 1 : 1.0 :x[1,1] + x[2,1] + x[3,1] + x[4,1] + x[5,1] + x[6,1] + x[7,1] + x[8,1] + x[9,1] + x[10,1] + x[11,1] + x[12,1] + x[13,1] + x[14,1] + x[15,1] + x[16,1] + x[17,1] + x[18,1] + x[19,1] + x[20,1] + x[21,1] + x[22,1] + x[23,1] + x[24,1] + x[25,1] + x[26,1] + x[27,1] + x[28,1] + x[29,1] + x[30,1] + x[31,1] + x[32,1] + x[33,1] + x[34,1] + x[35,1] + x[36,1] + x[37,1] + x[38,1] + x[39,1] + x[40,1] + x[41,1] + x[42,1] + x[43,1] + x[44,1] + x[45,1] + x[46,1] + x[47,1] + x[48,1] + x[49,1] + x[50,1] : 1.0 : True </code></pre> <p>Gurobi log:</p> <pre><code>x22053: 587140 rows, 21953 columns, 2317504 nonzeros Set parameter MIPGap to value 0.15 Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64) CPU model: AMD Ryzen 7 5800H with Radeon Graphics, instruction set [SSE2|AVX|AVX2] Thread count: 8 physical cores, 16 logical processors, using up to 16 threads Optimize a model with 587140 rows, 21953 columns and 2317504 nonzeros Model fingerprint: 0x7427a6f5 Variable types: 8653 continuous, 13300 integer (13300 binary) Coefficient statistics: Matrix range [8e-02, 5e+02] Objective range [1e+00, 1e+00] Bounds range [1e+00, 1e+00] RHS range [1e+00, 1e+03] Presolve removed 196104 rows and 8802 columns (presolve time = 5s) ... Presolve removed 200354 rows and 8802 columns (presolve time = 10s) ... Presolve removed 200354 rows and 8802 columns Presolve time: 13.18s Presolved: 386786 rows, 13151 columns, 1221701 nonzeros Variable types: 151 continuous, 13000 integer (13000 binary) Found heuristic solution: objective 118.1166667 Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 1.0250000e+02 0.000000e+00 8.600000e+00 25s 107 1.0250000e+02 0.000000e+00 0.000000e+00 25s 107 1.0250000e+02 0.000000e+00 0.000000e+00 25s 107 1.0250000e+02 0.000000e+00 0.000000e+00 25s Use crossover to convert LP symmetric solution to basic solution... Root crossover log... 8514 PPushes remaining with PInf 0.0000000e+00 25s 1154 PPushes remaining with PInf 0.0000000e+00 30s 0 PPushes remaining with PInf 0.0000000e+00 35s Push phase complete: Pinf 0.0000000e+00, Dinf 2.3045463e-11 35s Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 8624 1.0250000e+02 0.000000e+00 0.000000e+00 35s Root relaxation: objective 1.025000e+02, 8624 iterations, 12.16 seconds (10.88 work units) Total elapsed time = 60.91s Total elapsed time = 67.15s Total elapsed time = 73.27s Total elapsed time = 75.11s Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 102.50000 0 76 118.11667 102.50000 13.2% - 76s Explored 1 nodes (45160 simplex iterations) in 76.75 seconds (82.07 work units) Thread count was 16 (of 16 available processors) Solution count 1: 118.117 Optimal solution found (tolerance 1.50e-01) Best objective 1.181166666666e+02, best bound 1.025000000000e+02, gap 13.2214% </code></pre> <p>Edit: I have fixed the value of one x to 1 and then check the behaviour after this. The fix works and the value is 1 on the solution, but now I have noticed that some of the x values are not 0, but -0. I do not know what this means.</p> https://or.stackexchange.com/q/10859 1 Help with Mathematical Formulation for VRP with Specific Constraints Ilyass https://or.stackexchange.com/users/12309 2023-08-19T07:01:16Z 2023-09-23T11:07:51Z <p>I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers available to fulfill the pick up requirements. The problem has the following characteristics:</p> <p>I have a distance matrix between all 19 nodes and the depot. Each node has an associated demand representing the amount to be picked up. The pickers have a limited capacity of 25 units each. <strong>The capacity of each picker is less than the demand at every node</strong>, necessitating <strong>multiple trips</strong>.</p> <p>I am seeking assistance in formulating this problem mathematically. Specifically, I need help defining the constraints to ensure that the pickers efficiently complete their tasks <strong>while considering capacity limitations and multiple trips necessity</strong>.</p> <p><strong>Data:</strong></p> <ul> <li>Distance matrix: A 20x20 matrix representing distances between nodes and the depot.</li> <li>Demand: A list of 19 demand values, one for each node.</li> <li>Picker capacity: 25 units for each picker.</li> <li>Number of pickers: 7.</li> </ul> <p><strong>Goal:</strong><br /> Minimize the total distance traveled by the pickers while satisfying the pick up demands and capacity constraints.</p> https://or.stackexchange.com/q/10493 0 Linear Programming - Model understaffing mingabua https://or.stackexchange.com/users/11887 2023-05-28T22:40:19Z 2023-09-27T19:01:25Z <p>I am reading up a bit on Linear Programming and have taken a lot from <a href="https://link.springer.com/article/10.1023/A:1019009928005" rel="nofollow noreferrer">&quot;Scheduling Emergency Room Physicians&quot;</a> (by Michael W. Carter &amp; Sophie D. LaPierre, Health Care Management Science 4, 347–360 (2001)) for this.</p> <p>I have a question regarding constraint (3.2.2) from page 350. This constraint prevents understaffing and overstaffing. It goes as following: <span class="math-container">$\sum_{k=1}^{K}x_{ijk}=c_{ij}~\forall I,J$</span></p> <p>It indicates wether worker <span class="math-container">$k$</span> works shift <span class="math-container">$i$</span> on day <span class="math-container">$j$</span>.</p> <p>Introducing overstaffing could easily be done by changing the equality to <span class="math-container">$\ge c_{ij}$</span></p> <p>My question is, how do I change the constraint so that I can still allow for understaffing? Of course, the constraint should prevent that every shift is understaffed (<span class="math-container">$\sum_{k\in K}^{}x_{ijk}=0$</span>), because this would logically minimize the costs.</p> <p>I'm interested in how to introduce some understaffing, for example, that a physician can be admitted less than necessary, sort of as a lower minimum?</p>