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
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 ...
HunKhle's user avatar
  • 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?
Lin Sen's user avatar
  • 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
uni_lad's user avatar
  • 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 ...
best_bound's user avatar
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 ...
OR Junior's user avatar
  • 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, ...
Penghui Guo's user avatar
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 ...
Samira Fallah's user avatar
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 ...
Rebecca Donnelly's user avatar
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 ...
Kuifje's user avatar
  • 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 ...
gmn's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
Andrew's user avatar
  • 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 ...
J. Dionisio's user avatar
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 ...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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. ...
Pia MiA's user avatar
  • 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,...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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?
Samira Fallah's user avatar
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 ...
whitepanda's user avatar
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 ...
Pia MiA's user avatar
  • 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,...
Vala's user avatar
  • 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 ...
J. Dionisio's user avatar
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=\...
falamiw's user avatar
  • 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/...
Pia MiA's user avatar
  • 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. ...
Daniele Cuomo's user avatar
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 ...
Pia MiA's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
J. Dionisio's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Daniele Cuomo's user avatar
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 ...
Austin Buchanan's user avatar
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{...
user3390629's user avatar
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}...
gmn's user avatar
  • 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 ...
watchdogs132's user avatar
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 ...
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
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 ...
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
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 ...
jkschin's user avatar
  • 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*} ...
user1868607's user avatar
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 ...
AyamGorengPedes's user avatar
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 ...
maxime 's user avatar
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 ...
gmn's user avatar
  • 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 ...
user3711946's user avatar
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 ...
Kuifje's user avatar
  • 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 ...
Monotros's user avatar
  • 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 ...
stats_noob's user avatar
  • 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/...
stats_noob's user avatar
  • 1,821