Skip to main content

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
37 views

The first reference which formulated k-means problem as MIQCP using big-M constraint

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $P_1, P_2, \dots, P_N$ in $\mathbb{R}^d$, the problem is to find $K$ centres $Q_1, ...
MindaugasK's user avatar
0 votes
0 answers
39 views

Time complexity of QP solver

Could you suggest any papers or other resources that report the computational time complexity (e.g., O(n^3)) of the OSQP solver for Quadratic Programming (convex optimization), or at least the ...
Enk9456's user avatar
  • 11
1 vote
1 answer
43 views

Real problem in capacity planning in transport network - operational level

I need to find a real problem for my thesis and I'm reviewing the literature. The topic is operational capacity planning in transport networks. I understand I need to find a real-world problem at the ...
Trang Ly's user avatar
1 vote
1 answer
58 views

Reference request for different network types

I am trying to understand the mathematical models used in airline revenue management when a disruption occurs. The researchers are re-scheduling the resources(aircraft, flights etc.) in recovery ...
Learning's user avatar
2 votes
1 answer
127 views

In which circumstances is it sufficient to branch on the flow on edges to ensure integrality in VRPs?

I know that it is common to branch on the flow on arcs to ensure intergrality when solving VRPs, but in which circumstances is valid to branch on the flow on edges instead of arcs? References to ...
gmn's user avatar
  • 676
0 votes
0 answers
29 views

Theory of Contraints Technical Reference

I have dived into Theory of Constraints by reading The Goal, It's Not Luck, Isn't it Obvious, and Critical Chain. I am currently reading Goldratt's Rules of Flow. While I enjoy these short novels, ...
Galen's user avatar
  • 141
1 vote
0 answers
81 views

Coding Operation research algorithms

Can you suggest good books to refer regarding coding operation research algorithms like transportation algorithm, assignment algorithm etc What are the best practices for coding those algorithms
Tharindu Kariyawasam's user avatar
0 votes
0 answers
42 views

Proof of Dual Simplex Ratio Test

I have been trying to find proof of the ratio test for Dual Simplex, that is, selecting the variable that enters the base. Specifically, I was interested in knowing why by making that choice, reduced ...
Pedro García's user avatar
1 vote
0 answers
47 views

How to decompose the problem with overlapping blocks?

If the original problem contains the diagonal block structure property or other specific properties then we can apply column generation or other decomposition algorithms to solve it. However, if the ...
ytsao's user avatar
  • 386
4 votes
0 answers
95 views

Any recommendations for learning about polyhedra and integer programming?

My knowledge on convex polyhedra and systems of linear inequalities (facets, edges, Farkas Lemma, projections, duality, etc.) is very scattered, and I'l like to go through a book to solidify it. I'm ...
user56202's user avatar
  • 233
3 votes
1 answer
97 views

How to modify Benders decomposition to handle overlapping or shared variables among the subproblems

I have a problem that can be separated into a master problem and two subproblems, SP-A and SP-B. SP-B share some variables with SP-A, and the shared/overlapping variables from SP-A cannot be fixed for ...
user4444's user avatar
3 votes
0 answers
39 views

How Widespread Is the Application of MDPs in Medical Decision Making?

I'm curious about the current prevalence of Markov Decision Processes (MDPs) in medical decision-making. I've seen several research papers on this topic but was unable to find evidence of real-world ...
mdslt's user avatar
  • 615
1 vote
0 answers
110 views

Applications of Knapsack and Cutting Stock in Pure Math

I'm giving a seminar to PhD students in pure math, and one of the things I'd like to do is show that more applied optimization can also make its way into pure Mathematics. As for classical problems, I'...
J. Dionisio's user avatar
1 vote
1 answer
99 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
165 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
133 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?
uni_lad's user avatar
  • 39
6 votes
0 answers
141 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
84 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
  • 543
4 votes
3 answers
354 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
46 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
65 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
165 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
  • 13.5k
2 votes
1 answer
50 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
  • 676
1 vote
1 answer
52 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
31 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
  • 163
2 votes
0 answers
77 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
38 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
  • 390
1 vote
4 answers
2k 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
  • 390
2 votes
0 answers
38 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
  • 390
1 vote
1 answer
101 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
  • 390
0 votes
0 answers
61 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
  • 390
4 votes
0 answers
86 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
145 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
249 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
  • 390
2 votes
1 answer
136 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
81 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
225 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
278 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
  • 390
3 votes
1 answer
72 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
  • 390
0 votes
1 answer
180 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
  • 390
2 votes
0 answers
43 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
419 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
91 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
61 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
642 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
89 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
39 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
  • 676
5 votes
2 answers
310 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
115 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

1
2 3 4 5