Most Popular
1500 questions
6
votes
2 answers
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven't ever seen that this solution approach used to…
Bhr
- 455
- 2
- 7
6
votes
3 answers
How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?
A simple algorithm may be traverse all vertices, and perform DFS for every vertex.
However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the DAG, respectively. (Since $m \in O(n^2)$, the…
LighTofHeaveN
- 61
- 3
6
votes
0 answers
Provide basic solution to CLP
I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many iterations (in the range 300,000-700,000).
It's not hard…
Arjan Dijkstra
- 89
- 4
6
votes
0 answers
Cases where RLT/SDP relaxation does not work well with standard quadratic optimization
(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax the problem by convexifying the objective…
independentvariable
- 3,980
- 10
- 36
6
votes
1 answer
Asymmetric vehicle routing benchmark instances
Is there a standard set of asymmetric capacitated vehicle routing problem (ACVRP) benchmark instances similar to CVRP (http://vrp.galgos.inf.puc-rio.br/index.php/en/)?
The only thing I found were a few (easy) instances from Fischetti, et al. (1994)…
Matthew Galati
- 516
- 2
- 7
6
votes
1 answer
Complexity \ Reference request for variant of max flow problem
In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the cost of using this arc is given by…
batwing
- 1,458
- 6
- 15
6
votes
2 answers
Simplex algorithm and extreme points
For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form.
Since the Simplex algorithm iterates from extreme point to extreme point (corresponding to the fact that Simplex iterates from BFS…
t42d
- 201
- 1
- 1
6
votes
1 answer
Column generation approach for CVRP
I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about implementing column generation for CVRP that I…
Bhr
- 455
- 2
- 7
6
votes
1 answer
Column Generation algorithm for vehicle routing problem
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I want to know how I should write the path-based…
Bhr
- 455
- 2
- 7
6
votes
2 answers
What is the best way to read papers in OR/MS field?
I am a Ph.D. student in management science and I am interested in Dynamic Pricing. I need to define some problems and work on them as my thesis
Most papers in this field are full of complicated proofs covering different topics. If I read each paper…
Amin
- 2,150
- 7
- 20
6
votes
1 answer
Min-cost flow with per-edge flow conservation
I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint.
Instead of the summed outgoing flow equaling the summed incoming flow for each node:
$$\sum_i f_{i,n} =…
funky_capybara
- 103
- 3
6
votes
1 answer
Convexity of the variance of a mixture distribution
$X$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X \sim \sum_{i=1}^N w_i \cdot \mathbb{U}(x_i, x_{i+1}),$$
where $\mathbb{U}(x_i, x_{i+1})$ denotes a random variable that follows a uniform…
independentvariable
- 3,980
- 10
- 36
6
votes
1 answer
Conditions required for strong duality to hold for SDPs
According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."
What are the necessary conditions for strong duality to hold in semidefinite programming?
I would think this question would be…
kanso37
- 193
- 5
6
votes
1 answer
Does strong duality hold when I dualize only a subset of the constraints?
Suppose I know that for some non-convex program:
\begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align}
strong duality holds for this problem. Now, suppose I form the dual by only dualizing a subset of the constraints so…
George Chang
- 329
- 1
- 2
6
votes
2 answers
Linear objective function with non-linear constraints
I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type
$$
\underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\
$$
subject to the following…
FightMilk
- 215
- 1
- 5