# Tag Info

## Hot answers tagged operations-research

45

In general, elevator scheduling is a seriously difficult problem (see, e.g., this presentation and its list of references for some idea of its complexity). Your example situation starts to get at why it's hard: in order to know how often this happens, you need to know how quickly the elevator travels, relative to how often people arrive. And once it happens, ...

10

This can be formulated as a mixed-integer linear program (MILP; or sometimes just MIP). Number the resources $i=1,2,\dots, m$ and the providers $j=1,2,\dots,n$. Construct a matrix $C\in\mathbb{R}^{m\times n}$, so that the cost of resource $i$ from provider $j$ is $C_{ij}$. Let $\ell\in\mathbb{R}^n$ be a nonnegative vector of resource requirements; that is, ...

8

Your model concerns the "low frequency mode" of the elevators: The building is $n\geq1$ stories high, whereby the floors are numbered from $0$ to $n$. The elevators are at rest at floors $r$ and $s$ with $0\leq r<s\leq n$, and are waiting for the next customer. This customer will arrive with probability ${1\over2}$ at floor $0$, and with probability ${1\... 7 Of course$I-N$is not always invertible. Clearly, if$A$is a non-invertible function, then$N=I-A$causes$I-N=I - (I-A) = A$to be non-invertible. The thing is that the expression $$(I+N+N^2+\cdots)$$ makes no sense if$N$is not some special matrix. For example, if$N=I$, what is$I+N+N^2+\dots$? It equals an infinite sum of identity matrices and it ... 6 To guarantee a particular minimum grade, simply assume that every term you don't study will be on the test. For the example given, if every term not studied is on the test, to get 100%, you need to find 4 terms that you've studied, no matter which 10 terms appear. Hence you can only afford to skip 6 terms, and must therefore study$19-6=13$terms. More ... 6 You don't need big-M constraints for this purpose.$s_i=2b_i-1$should suffice. 5 Well spotted. In a case like this, it's a good idea to check the article's history (using the "View history" link at the top). In the present case, the error was introduced only two days ago by an anonymous user in this edit (which I just reverted). 5 Let the two sets of vertices be$X$and$Y$. If the equality subgraph does not have a perfect matching, it must violate Hall’s marriage condition, so there is some$X'\subseteq X$adjacent to fewer than$|X'|$vertices in$Y$. Let$Y'$be the set of vertices in$Y$adjacent to$X'$in the equality subgraph. The adjustment to the cover consists in replacing$...

5

Yes, it comes up in OR (typically in references to problems being NP-complete or NP-hard). It is worth understanding, particularly in terms of understanding the limitations of what P versus NP versus not even NP (cannot be checked in polynomial time) means. The distinction is an asymptotic one (in terms of problem size). Too many papers use "it's NP-hard" ...

4

If $n$ is even, $f$ has to be the sum $\sum_{i=1}^{n}{|p_i-c|}$ or a monotonically increasing function of this sum. Your requirement: $f(x_1,...,x_n)\le f(y_1,...,y_n)$ whenever $x_i=|p_i-c|$, $y_i=|p_i-d|$, and $c$ is median of $p$, written as $c=m(p)$. The vector $x$ represents distances from median location and vector $y$ represents distances from ...

4

Let $w,x,y,z \in \mathbb{Z}$ such that: $x,y,z \in \{0,1\}$ $x+y+z=1$ $w=-3x+7y+19z$ Then $w$ will be exactly one out of $-3,7,19$.

4

You can find a proof of the statement in the table that you quote in the book Linear and Integer Programming: Theory and Practice, Second Edition pages 141-145, proof of Theorem 4.5. However the exact statement is that existance of a degenerate and (additionally) unique solution of the primal implies multiple solutions to the dual. Using the ...

4

Let's represent your starting location as $0$ and the destination as $1000$. Let $f(x)$ be the greatest amount of fuel that can possibly be transported to or past $x$ miles from the starting point. For example, if you pick up $1000$ gallons, drive to $1$ (one mile), drop off $998$ gallons, drive back, repeat the trip to $1$ and back, and on the third trip ...

4

There are many ways to do this. Here are three: Option 1 Let $y_i$ be a binary that equals $1$ if and only if $x$ is in the $i^{th}$ interval ($i\in \{[0,1],[1,2],[2,3]\}$). The idea is then to express $x$ as a convex combination of the extreme points of the intervals. Therefore, we introduce variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3 \in \mathbb{... 4 You mix up the constraints. It should be $$0\le x\le 15,\quad 0\le y\le 4.$$ 4 Lets define$f_i$as the fraction of the total money bet on horse i: $$f_i \equiv \frac{x_i}{\sum x_i}$$ Then the conditions are $$a_if_i>1\ \ \forall i$$ And $$\sum f_i = 1$$ Assume for a moment that we want to get the same amount no matter which horse wins. Call the ratio of the winnings to the amount invested M. Then $$a_if_i -1 \equiv M \ \ \forall i$$... 4 Here is an approach when the$f$function is strongly convex with sufficiently large$c$: Let$f$be$c$-strongly convex for$c>0$. Let$b>0$be a parameter such that$g(x)+ (b/2)||x||^2$is convex. Suppose that$c>b$. Since$g(x) + (b/2)||x||^2$is convex, it follows that$g(x) + (b/2)||x-v||^2$is also convex for any constant vector$v$(since ... 3 Terminology differs, but "face" is generally not the same thing as "facet". Faces can have any dimension. In this case the$0$-dimensional faces (the "corners") have to be integer points. 3 Consider a "renewal time" as a time when the number of customers goes from$1$to$0$. After a renewal time, we wait Exponential($\lambda$) time in each of the states$0, 1_u, \ldots, (n-1)_u$: a total expected time$n/ \lambda$of which an expected time$1/\lambda$is spent in state$0$. Then the server becomes active, and we are in a "normal" M/M/1 queue ... 3 Linear programming is widely used in all sorts of fun transportation problems. These problems are not simple, but they are useful and interesting. An example off the top of my head: how do you effectively allocate bikes or cars as a public resource? Publicly available papers: Balancing Bike Sharing Systems with Constraint Programming Decision support for ... 3 Introduce a new variable$y$, and rewrite as follows: \begin{array}{ll} \text{minimize} & y \\ \text{subject to} & c_i^Tx + d_i \leq y, ~i=1,2,\dots, p \\ &A x = b \\ &x \geq 0 \end{array} 3 Not sure this is the best, but I would: load jeep up, travel 200mi, dump 600 gallons, go back to base repeat step 1) load jeep, go 200 mi. There is now 2000 gallons, 800mi from destination travel 333 1/3mi, dump 333 1/3gallons, go back to 800mi mark. load jeep, travel 333 1/3 mi. There's now 1000 gallons, 466 2/3 miles from destination travel 466 2/3 miles, ... 3 1. Lets show$x_q$can't leave the basis Intuitively If the row$s$contains all zeros except in the column of$x_q$, it means the problem contains a constraint of the type $$x_q = b_s$$ In that case, only solutions with$x_q = b_s$are feasible, so the variable$x_q$never leaves the basis. Mathematically$x_q$leaves if there is some non-basic ... 3 I went from engineering in telecommunications (where I heard a lot about MIMO systems) to operations research (where I saw lots of graph theory). To my knowledge, there is no definition of the terms "input" and "output" in graph theory that are currently used by the community, which means no MIMO. You may however look into: In directed graphs, a node with ... 3 Your notation is a bit confusing... so I could have some inputs wrong, please correct me if there are mistakes. We wish to optimize$x$, the palm oil fraction in Palmoil. We are given that: (1) For each liter of Palmoil, we get$\frac{10}{1+x}$km of performance. (2) Since palm oil costs \$0.3/liter and diesel costs \$0.5/liter, the cost of Palmoil is$0....

3

Your equation $C'=0$ does have a solution. Add $6$ to both sides, multiply by $\sqrt{x^2+2500}$, then square both sides, getting $$100x^2 = 36(x^2+2500)$$ which has the solution $x=300/8$.

3

The example you have given can be turned very easily into a linear programming problem. Version 1: Let Num1 be the number of Ticket1, Num2 be the number of Ticket 2 etc. Minimise TotalCost st TotalCost = 10 Num1 + 20 Num2 + 10Num3 Num1+Num3 $\ge 2$ (this ensures the correct number of adults) Num2 $\ge 3$ (this ensures the correct ...

3

In my view it is wrong. You have three resource constraints ($M_1, M_2, M_3$). First I define the variables. $x=$Amount of Perfect Grass in kg. $y=$Amount of Super Grass in kg. $m_i$=Amount of resource $i$ in kg. $\color{olive}{\text{contraints}}$ $m_1=2x+3y\leq 1500 \qquad (M_1)$ $m_2=x+2y\leq 1200 \qquad (M_2)$ $m_3=2x+y\leq 1300\qquad (M_3)$ \$x\...

3

Your problem has an element of the facility location problem I think. There is a constraint on the number of sources (facilities) you can open. In the general case there will be a cost of opening a facility (activating a source). Literature related to combining facility location with transportation might be helpful. This might be a decent starting point ...

3

First of all let me come back to your first attempt as I think that it is important to understand why it does not work. Then I will try to give you some pointers as to why the second set of equations is probably correct. Your first attempt at modeling the problem was as follows: \begin{align} p_P^{U_1} = c_A^{U_1} + 0.5~c_B^{U_1} \\ p_Q^{U_1} = 0.2~c_A^{U_1}...

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