Questions tagged [reference-request]

For questions asking for references from the literature or textbooks on specific topics.

Filter by
Sorted by
Tagged with
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)$ ...
dxb's user avatar
  • 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 ...
Kuifje's user avatar
  • 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 ...
user9151's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
Andrew's user avatar
  • 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 ...
J. Dionisio's user avatar
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 ...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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. ...
Pia MiA's user avatar
  • 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,...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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?
Samira Fallah's user avatar
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 ...
whitepanda's user avatar
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 ...
Pia MiA's user avatar
  • 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,...
Vala's user avatar
  • 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 ...
J. Dionisio's user avatar
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=\...
falamiw's user avatar
  • 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/...
Pia MiA's user avatar
  • 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. ...
Daniele Cuomo's user avatar
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 ...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
J. Dionisio's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
Austin Buchanan's user avatar
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{...
user3390629's user avatar
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}...
user9151's user avatar
  • 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 ...
watchdogs132's user avatar
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 ...
CesarGon's user avatar
  • 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 ...
ktnr's user avatar
  • 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 ...
falamiw's user avatar
  • 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 ...
jkschin's user avatar
  • 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 ...
jkschin's user avatar
  • 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*} ...
user1868607's user avatar
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 ...
AyamGorengPedes's user avatar
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 ...
maxime 's user avatar
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 ...
user9151's user avatar
  • 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 ...
user3711946's user avatar
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 ...
Kuifje's user avatar
  • 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 ...
Monotros's user avatar
  • 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 ...
stats_noob's user avatar
  • 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/...
stats_noob's user avatar
  • 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 ...
Cror2014's user avatar
  • 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 ...
stats_noob's user avatar
  • 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. ...
Andre's user avatar
  • 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 ...
Betty's user avatar
  • 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 ...
stats_noob's user avatar
  • 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,...
Michael Watson's user avatar
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 ...
2022's user avatar
  • 21