Questions tagged [reference-request]
For questions asking for references from the literature or textbooks on specific topics.
197
questions
1
vote
1
answer
84
views
Optimization algorithm for space debris
I'm currently working on a research project to optimize the recovery of space debris. We have to recover 50 pieces of space debris with the minimum number of missions possible. The missions are sent ...
- 11
1
vote
1
answer
131
views
Primal-Dual Simplex Algorithm
Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
- 25
2
votes
1
answer
84
views
logic constraints for IP model
I have been struggling with the formulation of logic constraints. Is there any source you would recommend to understand the topic better or trick of formulation of the constraints?
Thanks
- 39
6
votes
0
answers
139
views
What are some recommended Master's degree programs for individuals interested in specializing in the development of MI(L)P solvers?
There are tons of Masters programs across North America and Europe focused on OR/Industrial Engineering.
I am interested especially in solver technology and would be very grateful if someone could ...
- 61
2
votes
1
answer
79
views
Kim et al.'s (2006) waste collection VRP-IF
I cannot find a link for the instances of Kim et al.'s (2006) waste collection VRP-IF. https://www.sciencedirect.com/science/article/pii/S0305054805001322. The link mentioned in the paper and the ...
- 489
4
votes
3
answers
310
views
Systematic references on linearizing conditional / logical expressions
On this site, one can usually finds questions like “How to transform my expression into linear form?” The expressions usually contain and, ...
- 702
1
vote
0
answers
41
views
Seeking Assistance with Applying Benders Technique for Bilinear Problem Solving
I have two specific types of bilinear terms in the problem. The first type involves the multiplication of an integer variable and a continuous variable, while the second type involves the ...
1
vote
1
answer
61
views
What are the most popular papers on Uber-type spatial matching?
This is probably one of those "just google it" kinds of questions, but is there a commonly-accepted "definitive" model in the literature for capturing the kind of matching problem ...
4
votes
1
answer
145
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.9k
2
votes
1
answer
45
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 ...
- 622
1
vote
1
answer
50
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
23
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 ...
- 165
2
votes
0
answers
70
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
36
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
1k
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
35
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
87
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
56
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
85
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
142
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 ...
- 334
6
votes
2
answers
240
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
115
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,...
- 61
2
votes
0
answers
73
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
165
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
229
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
66
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
73
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
137
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
42
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
286
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
90
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
60
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
497
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 ...
- 606
2
votes
1
answer
88
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
36
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}...
- 622
5
votes
2
answers
297
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 ...
- 133
2
votes
1
answer
89
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
214
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
190
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
81
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
6
votes
1
answer
134
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 ...
- 421
6
votes
2
answers
473
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
5
votes
1
answer
126
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 ...
- 622
3
votes
1
answer
67
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
571
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.9k
7
votes
3
answers
734
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
462
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,821
4
votes
0
answers
192
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,821