Questions tagged [operations-research]
Operations Research, sometimes known as Management Science or Decision Science, is the discipline of applying appropriate analytical methods to help those who run organisations make better decisions.
782
questions
3
votes
0
answers
56
views
Linear sum assignment -- faster algorithms for a structured cost matrix?
The Hungarian algorithm for the linear sum assignment problem with dimension $n$ has complexity $O(n^3)$. Can the complexity be improved if one is able to assume that the cost matrix is structured? I ...
- 219
1
vote
1
answer
54
views
Why do we choose the maximum value instead of minimum?
Vogel's method selects the corresponding variable through a penalty. There is a penalty for each row and column and is the subtraction between the two lowest costs (in absolute value).
We must select ...
- 11
0
votes
0
answers
43
views
Geometric Proof About Constrained Minimization Problem
I got the following problem, but I have difficulties understanding part of its solution. I would really appreciate it if someone could explain it for me!
Problem
Present a geometric proof that in the ...
- 261
1
vote
1
answer
23
views
Particle Swarm: Restart a stalled particle near the "global best" or the particle's "local best" position?
I am working on an implementation of Particle Swarm that intelligently restarts a particle when its velocity reaches zero, so the particle can find a new starting point and continue its search. This ...
- 267
0
votes
1
answer
24
views
Maximizing Neighboring Count in a Sequential Grid Placement: A Combinatorial Optimization Problem [closed]
Given a 20x20 grid and an initial value of N = 0, we follow a certain strategy to place a piece into each cell of the grid sequentially. Upon each placement of a piece, we calculate the number of ...
- 3
1
vote
0
answers
23
views
Recent and interesting application of infinite series or inifite sequence in the optimization theory or any other area
I'm looking for an interesting application of Sequences and Series (theory from mathematical analysis) in the field of Operational Research, in particular involving combinatorics or linear ...
- 1,383
3
votes
1
answer
49
views
Managing warehouse based on how likely it is that products are ordered together
I am trying to solve a rather difficult issue at my job right now. We are interested in installing a set of automatic trays in our warehouse, each of which can hold $N \in \{5, 6, \dots, 20 \}$ unique ...
- 31
0
votes
0
answers
111
views
How to model the update-delay of observable variable in a model?
INFO: I have asked the same question last week at CS (here), but there is not even a single comment, so I am posting it here in hope someone might help with literature or approach.
I have a problem ...
1
vote
2
answers
55
views
Expressing locally linear in terms of integer programming
A locally linear graph $G=(V,E)$ is a graph whose adjacent vertices have exactly one common neighbor, i. e.
$$\forall(\{i,j\}\in E)\exists!(k\in V):\{i,k\}\in E\wedge\{j,k\}\in E$$
I'm trying to ...
- 1,493
1
vote
2
answers
30
views
Linear Programming for suppliers grouping
I have a set of suppliers each one with a set of products to be picked up with a certain quantity.
The objective is to know what suppliers to group with each other in order to minimize the distance ...
- 11
1
vote
2
answers
39
views
Max condition in Integer programming and MILP
Assume you have 2 binary variables $b$ and $c$. Suppose you want another binary variable, $a$ to be $\max(b,c)$ always. How would you represent this in the constraints of an integer program or of a ...
0
votes
0
answers
17
views
confusion in forming constraints to the product manufacturaing problem of operations research
In the OR problem statement attached below I am confused about the constraints to this problem.
The constraint on manufacturing is 10 hours of production per day.
so, if x->quantity of product 1 ...
0
votes
0
answers
12
views
Reddy Mikks new objective formation problem operations research
Am I thinking of the correct solution to the problem attached in Figure below of the Introduction to Operations Research book by Taha? I describe my approach to the problem in the attachment.
x->...
1
vote
1
answer
42
views
Operations research invert pyramid problem in minimum steps mathematical intutive solution to reach optimal solution
A (two-dimensional) pyramid is constructed in four layers: The bottom layer consists of (equally spaced) dots 1, 2, 3, and 4; the next layer includes dots 5, 6, and 7; the following layer has dots 8 ...
1
vote
1
answer
30
views
Minimizing maximum distance for integer case
I am working with different facility location models giving its single (only one center help a demand zone) and multi-source models (multiple centers can help a demand zone).
My decision variables are
...
- 169
0
votes
1
answer
68
views
Crossing the bridge puzzle mathematical solution
I have been trying to understand the mathematical solution to the Operation Research crossing the bridge puzzle. I was reading and trying to understand the solution given in the following paper
http://...
1
vote
1
answer
72
views
Minimizing the cost of generating a certain amount of power
I am working on electricity generation. I have $n$ motors and must produce a given amount of power:
Let the rotational speed of the $i$-th motor be denoted by $\omega_i$. For each motor, there is a ...
- 11
0
votes
0
answers
20
views
Assignmentproblem with multiple precedence constraints
Crossposted at Operations Research SE
The objective is to load as many passenger vehicles as possible on an auto-train.
The train has two levels and both are constrained in terms of length (sum of ...
- 11
0
votes
0
answers
23
views
Modeling of a special form of the precedence constraint
Crossposted at Operations Research SE
There exists a scheduling problem in which some tasks should be processed on some resources. Additionally, each task needs to be assigned to a specific position ...
- 117
0
votes
0
answers
61
views
Portfolio optimization with max information ratio. (cvxpy library not giving answer for particular cases)
In portfolio optimisation with maximizing information ratio, our aim is to create a portfolio such that the information ratio of the portfolio and corresponding benchmark is maximized. Information ...
- 113
0
votes
0
answers
14
views
Prove commutative of entanglement of two natural numbers.
I have defined an operation for entanglement of two natural numbers.
It is: $a$ T $b$
Example part 1 of 3:
$$
13 \\
24 \ \ \ \
$$
$$1 * 4$$
Example part 2 of 3:
$$
13\\
24
$$
$$1 * 2 + 3 * 4$$
...
- 117
0
votes
2
answers
66
views
Model legal shift constraints
I need your help.
My decision variable $b_{fds}$ indicates whether a fireman $f$ works shift $s$ on day $d$. I need two constraints:
a) No more than 5 consecutive working
days
b) At least 2 ...
- 3
0
votes
2
answers
104
views
Modelling a shift change
I have the following problem. I am currently modeling shift schedules. There is the variable $x_{itk}$ which tells whether the cashier $i$ completes the shift $k$ on day $t$. Now I want to model the ...
0
votes
2
answers
55
views
Linear program for non-zero combination of solutions
I am creating a linear program to find the optimal solution that is a combination of $3$ variables but due the constraints I have the optimal solution is just a combination of a non-zero value of one ...
1
vote
2
answers
114
views
Problem with case distinction in a programming problem
Good evening, I have the following problem. I want to create a duty roster and model performance losses. For this I have introduced the binary variable $l_{it}$, which takes the value 1 when the shift ...
1
vote
1
answer
34
views
How to efficiently solve a set of precedence networks at the same time?
I'm having a problem where I have a set of precedence networks.
Each networks consists of a number of nodes which have a duration, and type.
There are also a number of workers, who each have a type ...
1
vote
0
answers
35
views
Lagrangian function and first order necessary optimality conditions
I am given the following equality constrained convex QP.
$$\min_x \frac{1}{2}x'Hx+g'x$$
$$st. A'x+b=0$$
with $H\succ 0$.
I want to find the Lagrangian function for this problem and the first order ...
1
vote
1
answer
69
views
In linear programming, given an optimal unique solution, is it possible to obtain multiple optimal solutions by adding a new constraint?
In post-optimal analysis, when I already have an optimal solution (unique solution). I can add a new constraint and obtain multiple optimal solutions, but only if the new constraint eliminates the ...
- 41
0
votes
1
answer
43
views
Precedence constraints in assignment problem
I am struggling to model my problem correctly since multiple days.
Maybe someone can give me a hint.
I have two levels, both with a fixed number of slots (i.e. 200 each).
The items I want to put on ...
- 11
0
votes
1
answer
56
views
Determine the daily production program that maximizes the company's output
Crossposted at Operations Research SE
The mechanical workshop can produce $600$ units of part #1 or $1200$ units of part #2 per shift. The production capacity of the thermal workshop, where these ...
- 3
4
votes
1
answer
113
views
Knapsack budgetting
The problem
I have $1000 of money.
With it I can buy 3 items:
Item 1 which costs 45 dollars.
Item 2 which costs 75 dollars.
Item 3 which costs 25 dollars.
I want to know the optimal amount of each ...
- 145
-1
votes
1
answer
177
views
Why is Operations Research considered mathematics? [closed]
Today I learned that there exists a field called Operations Research that is supposed to be a field of mathematics according to sources such as Wikipedia.
Could someone explain to me, what is ...
- 8,148
3
votes
2
answers
98
views
Find the Minimum of: $\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=1}^n q_i a_i$
I'm confused with the following problem when doing my research.
Given $g_i,i=1,2,..,n-1$ and $q_i,i=1,2,..,n$, find the minimum of:
$$\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=...
- 83
0
votes
1
answer
67
views
How to write dual program to university course scheduling problem?
I am dealing with a type of scheduling problem - we need to schedule $n$ courses with length $p_1$, ..., $p_n$ into three classes $S_1$, $S_2$, $S_3$ with the use of linear programming. I already did ...
0
votes
1
answer
45
views
Graph Optimization Problems
I'm having a bit of trouble finding any references in the literature about optimizing functions defined on the set of graphs, i.e. in particular where the number of vertices is not fixed. For example, ...
- 431
0
votes
0
answers
20
views
Does there exist an MDP policy with this property?
Consider a discrete-time MDP with finite states and actions. For any policy $\pi$ and state $s$, let $u_t^{\pi}(s)$ be the expected total reward for using $\pi$ at times $t, t+1, ..., N$ if the ...
- 11
0
votes
1
answer
42
views
Optimal solution to the primal and the Lagrangian dual when there is duality gap
Consider the primal problem $\max_{x\in\mathcal{X}} f(x)$ subject to $g(x)\leq 1$ and its Lagrangian dual $\min_{\lambda\geq 0}\max_{x\in\mathcal{X}}\{f(x)+\lambda(1-g(x)\}$ with no convexity ...
- 377
0
votes
1
answer
82
views
How to maximize the amount of money at the end of the week?
This is the statement of my problem:
A new financial product is made so that if you invest X thousands of pounds a day, and a third more the next day, the third day we would recover triple of the ...
- 11
0
votes
1
answer
88
views
A simplified production model problem
I am struggling with a simplified production model problem and I am hoping someone can help me out.
The problem involves a plant that has three components: water purification, electricity production, ...
- 37
0
votes
3
answers
65
views
How to avoid discontinuous path?
I have a mid-size two sided network, and am just trying to run a simple routing. $x_{i,j}^d$ takes a value of one if $d$ travel from $i$ to $j$. Each driver starts from origins $s_d$ and finishes at $...
- 187
2
votes
2
answers
65
views
Integer Programming - How to express a conditional variable whose properties change once a value has been reached.
I have the following question. In an exercise they tell me:
You have the following product B that brings $25 of profit per unit, and takes a production time of 2.1 man-hours per unit to produce.
...
- 23
1
vote
1
answer
46
views
How to subtract a common path cost?
I have a simple pickup and delivery (PDP) model operating on a service provider that has multiple locations for providing service. My decision variables and parameters are as follows:
$\delta_{i,j}^d$...
- 187
1
vote
3
answers
80
views
Optimizing investments using linear programming
I'm given the following linear programming problem:
...
- 25
2
votes
1
answer
236
views
A power allocation problem
Given $t > 0$, let the function $f : \Bbb R_0^+ \times \Bbb R_0^+ \times[0,1]\times[-1,0]\to \Bbb R$ be defined as
\begin{align}
&f(x,y,\rho_1,\rho_2)=\frac{(t+1)\left(x\left(1-\rho_1^2-\rho_2^...
- 81
0
votes
0
answers
25
views
Find a facet for the maximum weight matching problem in a not oriented graph
Consider the problem of finding a maximum weight pairing in a graph
unoriented G = (V, E), where V is the set of its vertices and E the set of its
edges. In such a problem, we associate a weight pe to ...
- 13
2
votes
2
answers
84
views
Several questions on Column Generation: degeneracy, columns in/out and non-integer solutions
I am currently using Column Generation accompanied with Dantzig-Wolfe decomposition to solve MILP. I have several questions to ask.
At the beginning, the objective value of RMP does not improve even ...
- 41
1
vote
0
answers
81
views
Covering a rectangle using squares
Given a set of Squares $\mathcal{S}=\{w_1, w_2, \ldots, w_n\}$ and a rectangle $\mathcal{R}$ of dimensions $a\times b$.
Is there a placement of the squares in $\mathcal{S}$ to cover $\mathcal{R}$.
The ...
- 111
0
votes
1
answer
96
views
A quandary concerning "Exploring Mount Neverest"
Mission: To find a minimum-length walk, for one person alone, that covers the entirety of a simple closed curve c distance units long and that begins and ends at a particular point B on that curve, ...
- 39
1
vote
0
answers
74
views
Expected idle time of a server in an M/M/N queue
Consider a standard M/M/N queue where the jobs' arrival rate is $N\lambda$, the service rate of each of the $N$ servers is $1$, and $\lambda < 1$.
When a new job arrives, assign it to an idle ...
- 1,457
1
vote
1
answer
37
views
Percentage Jobs drop in $M/M/1 K$ Queue with Finite Queue Length
In my simulation of the $M/M/1 K$ Queue, the arrival rate $\lambda$ is $2.7\ \mathrm{ jobs/s}$ while the service rate $\mu $ is $3 \ \mathrm{ jobs/s}$. The capacity $K$ of the buffer is $5$. I am ...
- 13