Questions tagged [reference-request]
For questions asking for references from the literature or textbooks on specific topics.
190
questions
1
vote
0
answers
34
views
Classifying a particular kind of stochastic counting process
Let $N(t)$ be a stochastic process with the following properties:
If $N(t) < f(t)$, then $N(t)$ behaves as a homogeneous Poisson process with rate $\lambda$.
If $N(t) \geq f(t)$, then $N(t)$ ...
- 1,799
4
votes
1
answer
90
views
What are some good references of OR techniques applied to revenue management?
For teaching purposes, I am looking for some nice examples of revenue management problems which are tackled with optimization techniques, ideally linear programming (including MIPs).
For example, this ...
- 12.3k
2
votes
1
answer
43
views
When is $\max_x\{f(g(x))\} = f(\max_x\{g(x)\})$?
What is the requirements on $f$ and $g$ in order for $\max_x\{f(g(x))\} = f(\max_x\{g(x)\})$ to be correct?
Equivalently, when is $\min_x\{f(g(x))\} = f(\min_x\{g(x)\})$ ?
Any reference for describing ...
- 519
1
vote
1
answer
47
views
Does cutting a minimum spanning tree generate two minimum Steiner tree?
I am trying to understand whether this intuition is true or false.
Given a minimum spanning tree (MST) of an undirected positive graph $G=(V,E)$.
Consider a MST $T\subseteq G$. Removing any single ...
- 561
1
vote
0
answers
19
views
Understanding queueing theory used to model the vehicle routing problem
I am trying to understand some journal articles on the vehicle routing problem, specifically Vehicle routing with dynamic travel times: A queueing approach and An M/M/c queue model for vehicle routing ...
- 133
2
votes
0
answers
63
views
Dantzig-Wolfe decomposition survey/literature review
I was trying to find a literature review on Dantzig-Wolfe decomposition but was unable to do so. I found one on Benders, and another on Column-generation.
EDIT: If there is none, is there a paper that ...
- 516
1
vote
0
answers
34
views
Budgeted uncertainty on the RHS
Suppose we consider budgeted uncertainty (Bertsimas and Sim, 2002) for the following scenario. We have a binary decision variable $x_{i,j}$, where $i \in I$ and $j \in J$ (two sets). We then have the ...
- 392
2
votes
3
answers
244
views
Identifying the minimum number of required machines to schedule jobs
I am relatively new to the topic of optimization. I am currently trying to address the following problem:
We are given a set of jobs, say $J$ with release times, deadlines and duration. Jobs can be ...
- 392
2
votes
0
answers
28
views
Recoverable Robustness for an optimization problem
I am relatively new to the concept of recoverable robustness. I am researching the robust version of an optimization problem. I currently have methods to address the problem with perfect knowledge. ...
- 392
1
vote
1
answer
59
views
Scheduling tasks to minimize the total number of utilized cores
I currently have a scheduling algorithm which computes an approximate solution, say S, for the nominal scenario of a given problem instance, say N. Given that N changes in a way and becomes infeasible,...
- 392
0
votes
0
answers
55
views
Gamma uncertainty in the RHS of a constraint
I am new to the concept of robust optimization.I am trying to formulate the robust variation of a Binary Integer Program. Suppose we have a constraint of the form $\sum{x_{i,j}} \geq b_j$ for $ i \in ...
- 392
4
votes
0
answers
83
views
The study of directional derivatives for functions that are minimums of convex functions
Has there been any research on the topic of directional derivatives of functions that are minimums of convex functions?
2
votes
3
answers
137
views
Definition of a modified scheduling problem where jobs are halted based on the shifts of employees
I am looking for the name of a scheduling problem in literature with some references. Here is the variant that I have in mind.
Given a set of jobs, employees have certain shifts that they can work on ...
- 292
6
votes
2
answers
233
views
Robust optimization for IP formulation
I am researching the robust version of a problem. I have managed to produce an Integer programming formulation which solves the problem with perfect knowledge. From my research on the topic one can ...
- 392
2
votes
1
answer
83
views
How should I implement Benders Decomposition with annotations in C++ using CPLEX library
I'm a beginner in C++ and want to implement Benders decomposition in C++ using CPLEX. I'm gonna use it for a special case study, so I need to customize the cuts to minimize the optimality gap. However,...
- 41
2
votes
0
answers
70
views
Benders with MINLP subproblem as the pricing problem of Dantzig Wolfe
I have a convex MINLP that after a Dantzig-Wolfe reformulation, passes most of the difficulty onto the pricing problem, which becomes a convex MINLP itself.
The pricing problem should be solvable with ...
- 516
2
votes
1
answer
120
views
Difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming?
What is the difference between Optimality cuts and Feasibility cuts for L shaped method in stochastic programming? Like for the following problem they used Optimality cuts,
$$
\begin{aligned}
& z=\...
- 157
3
votes
2
answers
174
views
Modifying and re-optimizing a model using CPLEX Python API
I came across the following functionality that is offered by CPLEX for modifying and re-optimizing a model based on previous computations: https://perso.ensta-paris.fr/~diam/ro/online/cplex/cplex1271/...
- 392
3
votes
1
answer
63
views
Steiner tree sub-optimal algorithm always finds the optimal solution. Why?
I am using the algorithm implemented by the library networkx to solve a Steiner minimal tree problem.
They claim their algorithm to give an approximated solution.
...
- 561
3
votes
1
answer
70
views
Can we turn a Binary IP model into a problem solvable using Local search?
I am new to the fields of operations research. I have a Binary IP model for solving a scheduling problem and I am seeking to find information whether I can somehow transform it to a problem that can ...
- 392
0
votes
1
answer
107
views
Rolling Horizon approach for solving a job scheduling problem
I am trying solve a scheduling problem adopting a rolling horizon approach. I have developed an Integer programming model and seek to speed up execution.
I am seeking advice on beginner level ...
- 392
2
votes
0
answers
41
views
Shortest (undirected) path constrained to a sub-set of nodes
I expect this to be an NP-complete problem, as it may reduce to the Hamiltonian Path problem.
Anyway, I was wondering whether there exists some study and (aproximated) solutions for this particular ...
- 561
5
votes
1
answer
197
views
Dantzig-Wolfe vs Benders Decomposition on the dual problem - Computational differences
My question is a follow-up to this one: Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition. Here what is being discussed is the relationship between the two methods, and it is ...
- 516
3
votes
1
answer
89
views
On a clarification on usage of inequalities in convex programming
The inequality $x^3\leq y$ is not convex. But $0<x$ added to the above provides a convex region.
My question is whether in convex programming it is allowed to use both inequalities together and use ...
- 131
2
votes
1
answer
56
views
Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem
At page 7 from these slides there is a Greedy algorithm I want to implement.
It says
let $P_i$ be the shortest path (if one exists) that [...]
connects some ($s_j$, $t_j$) pair that is not yet ...
- 561
8
votes
1
answer
378
views
Good references for reduced cost fixing?
Reduced cost fixing is a technique used by mixed integer programming (MIP) solvers to safely fix variables to certain values. While this technique is well-known among the MIP community, I don't know ...
- 596
2
votes
1
answer
86
views
Decision Variables becoming Constraints
Consider a convex optimization problem with decision variable x. Though I'm interested in answers for any kind of convex optimization problem, let's say it's an LP, so we have something like:
\begin{...
- 121
3
votes
1
answer
31
views
Requesting references about recursive functions where the variables are continuous
I have a recursive function that looks something like this. The variable x is a continuous variable. Do anyone have a reference that looks into a similar problem? $$f_i(y)=\min_{0\le x\le\overline{X_i}...
- 519
5
votes
2
answers
285
views
Can Local Search Operators be formulated as a Mixed Integer Program?
Consider the situation of Vehicle Routing. Once we have an initial solution, one can apply various local search moves to improve it.
For example:
Removing a single customer from a route and inserting ...
- 123
2
votes
1
answer
70
views
Method to test compatibility between variable values
I have a problem with my current research that I have come across repeatedly over my research career in various different fields. It goes like this.
You are trying to characterise instances of some ...
- 123
2
votes
1
answer
38
views
Optimality guarantees/approximation ratios for simple dynamic capacitated lot-sizing problems
I once read a paper stating that under certain conditions, some simple variants of dynamic capacitated lot-sizing problems can be decomposed into subproblems along the temporal dimension and solved ...
- 491
2
votes
1
answer
149
views
Resource which explain different stochastic method with some intuition
Hope my question fit this community. I have taken Stochastic Optimization course (2 credits). The course content are:
Deterministic VS Stochastic Linear Program
Two-Stage Recourse Problem
Multi-Stage ...
- 157
14
votes
4
answers
2k
views
Where is the original Dantzig Simplex 1947 paper?
I see from here and many other sources that Dantzig invented the Simplex method in 1947. After much searching, I found that the earliest publication is this in 1956. Does anyone know where the ...
- 335
6
votes
1
answer
133
views
When was the exploration and exploitation tradeoff first mentioned in literature?
I've recently been exploring Reinforcement Learning (RL) methods in my work and the exploration-exploitation dilemma is always mentioned. It almost feels like the exploration-exploitation dilemma ...
- 335
3
votes
1
answer
72
views
Methods to solve integer linear inequalities with products of two variables
I'm interested in solving the following system of equations over the integers:
\begin{align*}
x_l^3 &\le x_l^1x_l^2 & \text{ for } l = 1,\ldots,s \\
A x &\le b \\
0 &\le x
\end{align*}
...
- 173
5
votes
1
answer
118
views
Modulo Integer Programming, $m$ equations $n$ variables
I am following 'Application of Number Theory to Numerical Analysis', and there is a section by G.H. Bradley called 'Modulo Optimization Problems and Integer Linear Programming'. There he explains that ...
- 401
6
votes
2
answers
436
views
Fleet Management: How to allocate vehicles between departments
Assume that I have data about a regular big company (not a salesman problem). data contains of every department's (marketing, finance, production, etc.) vehicle size, GPS track values, duration of ...
- 63
3
votes
0
answers
43
views
Complexity of the ellipsoid method in general convex problems
The ellipsoid method is often mentioned in relation to the complexity of solving linear programs.
Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
- 519
3
votes
1
answer
64
views
studies to determine how much customers can wait to get outputs from a real time optimization model
I am building a web-based tool that needs to take input from the user and run an optimization model on a server and display results back on the webpage. Currently it is a MIP formulation solved using ...
- 305
8
votes
3
answers
493
views
How to tackle this VRP variant?
I am currently working on the following problem, which is a variation of a vehicle routing problem. I am looking for different ideas to tackle it.
Problem description
A set of nodes with a given ...
- 12.3k
7
votes
3
answers
577
views
Combining Multiple Cost Values in Shortest Path Problem
I am trying to solve a shortest path problem through Dijkstra's algorithm. However in my case, cost between nodes (nodes $i$ and $j$) are more than one- two nodes are compared based on two different ...
- 179
10
votes
2
answers
364
views
The First Ever Linear Programming Problems
I have heard that Linear Programming was first used by:
Dantzig to solve problems involving US military logistics in the Second World War
Kantorovich to solve problems involving transportation of ...
- 1,811
4
votes
0
answers
184
views
Understanding Optimal Transport Problems
I am trying to better understand the origins of Optimal Transport Problems such as Monge's Problem.
For instance, I came across the following references:
https://www.math.ucdavis.edu/~qlxia/Research/...
- 1,811
3
votes
1
answer
62
views
Departure process of M/G/1 queue with hyper-exponential service times
I am working on two queues in tandem; the first queue is M/G/1 with hyper-exponential service times and the second queue has exponential service times. I want to know if the second queue can be ...
- 131
2
votes
1
answer
105
views
Traveling Salesman Reference
Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase?
I have informally ...
- 1,811
4
votes
2
answers
234
views
is there any recommended "rolling horizon in optimization" literature for beginners?
I am relatively new to optimization and mathematical programming. I am looking for literature on rolling horizon. When I search for it on the internet, I find many articles like:
Lukas Glomb et al.
...
- 293
8
votes
3
answers
520
views
Difference between "Online Optimization" and "Stochastic Optimization"/"Robust Optimization"?
I just came across the notion of Online optimization (I got a look on Wikipedia page and some other webpages), but it was not enough for me and I am looking for a more elaborated comparison, namely in ...
- 534
3
votes
1
answer
143
views
Reference of Optimization in the Bible : Moses and Coins
A few days ago, I was reading some articles/stackexchange posts on the "history and origins of optimization". Somewhere, there was an interesting reference to a biblical/old testament story ...
- 1,811
6
votes
2
answers
242
views
I'm looking for materials to share with undergrads who want to consider a career or masters degree in OR
My daughter is a math major at a good liberal arts school. It doesn't seem like they have any OR courses or talk much about it as a career choice (either for a job or going to grad school in OR.) And,...
- 811
2
votes
1
answer
167
views
What is the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?
I'm struggling with this question for weeks:
What is the main difference between the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?
I try to answer ...
- 21