Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
11
votes
1 answer

Incorrect solution for Vehicle Routing Problem in or-tools

I am trying to understand how the Vehicle Routing Problem is solved in OR-Tools. Using the example given here, I have tried to solve the following distance matrix with 9 separate vehicles: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1,…
Joba
  • 211
  • 1
  • 5
11
votes
4 answers

What are the benefits of linearization?

So I am new to OR (not my field, but I have found myself working in it for a thesis project). My problem is a non-linear problem by design and unfortunately I cannot linearize everything, however, there are parts of my problem that I can linearize…
GrayLiterature
  • 2,309
  • 7
  • 27
11
votes
3 answers

Modeling the Choose function

In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose equality constraint $${x \choose y} = C$$ without…
Josh Allen
  • 725
  • 3
  • 14
11
votes
2 answers

In portfolio optimization, how do we estimate the variance of a new asset?

Say I want to do Portfolio Optimization using the mean-variance approach (i.e Markowitz model), but that some of my assets are new with no returns history. I can use a judgmental (expert knowledge, not statistic based) forecast to come up with mean…
Skander H.
  • 2,139
  • 2
  • 11
  • 21
11
votes
1 answer

Solvers and saddle points

It seems like most solvers that can tackle nonlinear nonconvex optimization problems (e.g. IPOPT) operate on ultimately solving for the first-order optimality conditions. Can it therefore be assumed that these solvers do not guarantee convergence to…
Josh Allen
  • 725
  • 3
  • 14
11
votes
5 answers

Dealing with non-overlapping constraints

Let us consider the following problem: Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$ and a target start time $s_t$. No two tasks can be executed in parallel. The objective is to minimize the sum of the absolute deviation…
Renaud M.
  • 2,408
  • 1
  • 11
  • 27
11
votes
3 answers

Parallel nonlinear solvers

I've noticed that parallel (CPU or GPU) nonlinear programming solvers are few and far between. It seems that if any parallelization is involved at all, it generally applies to solving the underlying linear system or using multi-start methods. Is…
Josh Allen
  • 725
  • 3
  • 14
11
votes
4 answers

Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of the form "When instances of problem $\Pi$ satisfy…
ydubey7
  • 579
  • 2
  • 9
11
votes
2 answers

What is the difference between job shop scheduling and resource constrained project scheduling?

I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of problems. Understanding this difference would be a…
cdrootsudormstardashr
  • 113
  • 5
11
votes
2 answers

Generalized Assignment Problem as the sub-problem

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable? Moreover, is there any usage of this problem as a sub-problem within a decomposition…
Junior MIP
  • 400
  • 1
  • 10
11
votes
4 answers

Proof of bound on optimal TSP tour length in rectangular region

Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says: If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then $$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+b).$$ Here, $T^*(X)$ is the length of the optimal…
LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
11
votes
0 answers

Characterizing the solution of a (non) linear maximization program

I have the following maximization program \begin{align} \max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\ \text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \alpha_i}x_{ij} & j=\{1,\dots,J\} \\ q_i \geq 0 &…
Patricio
  • 591
  • 3
  • 9
11
votes
2 answers

Difficulties with finding equivalent problem on literature

I'm working with a sort of pickup delivery problem right now. We need to assign vehicles to routes and requests to those vehicles. Each request has its due date, client and may be delivered in one of multiple possible trips departing from depot time…
seimetz
  • 513
  • 2
  • 9
11
votes
1 answer

I've formulated my optimization model; now what?

I've formulated my linear/nonlinear/integer/mixed-integer optimization problem in algebraic form (possibly with the help of the folks on this site). Now what? How do I solve it?
LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
11
votes
2 answers

Is there a fixed worst-case error bound for farthest-insertion?

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form: $$\frac{z^H}{z^*} \le \eta,$$ where $z^H$ is the objective value of the solution returned by the heuristic for a given…
LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
1 2 3
…
99 100