Most Popular
1500 questions
8
votes
1 answer
Choosing better objective function for vehicle routing problem
I have a graph $G$ and the following variables.
$b_{i,j}$ is $(i,j)$ edge is taken or not.
$t_{i,j}$ is time to travel $(i,j)$
$A_{i}$, $D_{i}$ are arrival and departure time at node $i$.
My first objective is :
$$\min \sum_{i,j} b_{i,j}\cdot…
ooo
- 1,589
- 4
- 12
8
votes
1 answer
Safety stock when there is uncertainty in order completion
Safety stocks account for uncertainty both on demand and provider lead times, but never mention how to include the effect of incomplete orders. For example, what would happen if a provider always delivers on time but on average orders have 50% of…
Benjamín J Barros G
- 81
- 2
8
votes
1 answer
Diving heuristics in branch and bound
I am reading about extensions on plain vanilla B&B and heuristics for smaller trees/better branching. I have come across diving heuristics, which on the SCIP site is defined as:
A diving heuristic explores a single probing path down the search…
VincFort
- 183
- 4
8
votes
2 answers
Bounding arrival time at a node in a resource-constrained shortest path problem
Given a city map (a graph) $G$,
$b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$.
The objective is to move from $s$ to $e$ in minimum time. (I am trying an add intermediate…
ooo
- 1,589
- 4
- 12
8
votes
2 answers
Solving multiple easy ILP instances
I have an application where I am solving millions of ILP instances that differ from each other only on one constraint. The instances, of course, are relatively easy to solve or otherwise this would be hopeless. Their size is less than 1000…
Laakeri
- 189
- 4
8
votes
1 answer
Precedence Constraint in OR-Tools
I'm trying to write this constraint in C++ and add it to my model (addLessOrEqual):
$$\text{start}_{i}+\text{duration}_{i}\le\text{start}_{j}$$ for an $(i,j)$ arc of precedence.
Starts (IntVar) and durations (int) are part of an IntervalVar. The…
Diego R. Troncoso
- 635
- 4
- 13
8
votes
2 answers
Convex Optimization: Separation of Cones
I am trying to solve Exercise 2.39 at Boyd and Vandenberghe's Convex Optimization book. In one source, the answer is given as:
2.39 Separation of cones. Let $K$ and $\tilde K$ be two convex cones whose interiors are nonempty and disjoint. Show that…
independentvariable
- 3,980
- 10
- 36
8
votes
1 answer
Finding the optimal, spatially compact set of grid cells
I have a regular grid of cells, maybe square, maybe hexagonal.
Each cell has a numeric value associated with it.
How can I find a subset of cells that are:
a connected, compact set and
have an optimally high sum of values and
made of a number n…
inc42
- 189
- 2
8
votes
1 answer
Speed of convergence for minimizing Rosenbrock's function
I am minimizing $f(x_1,x_2) = 100(x_2-x_1^2)^2 + (1-x_1)^2$, where I try many algorithms to compare with each other. All of the algorithms find the optimal solution $(1,1)$ quickly, so I am not bothered with asymptotics right now.
Let $x =…
independentvariable
- 3,980
- 10
- 36
8
votes
1 answer
Why isn't $x_2+x_3+x_4\le 2$ a cutting plane?
In my textbook, to generate cutting planes, they tell you to proceed as follows:
A procedure for generating cutting planes:
Select a ($\le$) constraint that has only nonnegative coefficients.
Find a group of variables such that
a) The constraint…
Slim Shady
- 107
- 14
8
votes
1 answer
Dynamic programming example
I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK
for the next 4 years. I am considering the possibility of being a customer of company A which
sells BMW models. Not only I can buy a car from this…
Slim Shady
- 107
- 14
8
votes
2 answers
How to change the search strategy in a B&B framework, i.e., start with depth first and then continue with best node?
Is there any implementation, code or software, which can switch between search strategies in a B&B framework?
Majid
- 366
- 4
- 10
8
votes
1 answer
Travelling salesman problem with given number of locations to visit
There's a great example here of how to find a solution to the travelling salesman problem:
"""Simple travelling salesman problem between cities."""
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from…
ignoring_gravity
- 271
- 1
- 5
8
votes
4 answers
Disciplined convex programming representation of $x\sqrt{1-x}$
Anyone have an idea for a disciplined convex programming (DCP) representation of the concave function $x\sqrt{1-x}$, which is defined over the domain $[0,1]$?
The Taylor series about $x=0$ is $$x - \frac{x^2}{2} - \frac{x^3}{8} - \frac{x^4}{16} +…
Dan Berkenstock
- 81
- 2
8
votes
1 answer
Speedup or Caching for a Multi-Iteration MIP problem
I'm solving an MIP:
\begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $A$ and vector $x$ are boolean valued, and $A$ is symmetric (adjacency matrix).
I am then solving this…
Vidak
- 183
- 5