Most Popular
1500 questions
7
votes
1 answer
How to enforce a relation between two variables
I am having trouble formulating the following constraint:
I am looking to formulate a constraint that if a facility was opened at some point in time, then $Y[j,t]$ does always have to be $1$ from that point in time onwards (see values below). How do…
user7258
- 73
- 4
7
votes
2 answers
Which approaches exist to solve a TSP?
Exists a list of categories that include possibilities to solve a travelling salesman problem (TSP)? I know, for example:
Exact methods
Integer Linear Programming
Dynamic Programming
Constraint Programming
Heuristics
Construction…
maxmitz
- 659
- 3
- 11
7
votes
1 answer
Extreme rays of a small polyhedral cone: How do I get them?
In a nutshell
I have a small 2-dimensional polyhedral cone.
$$C=\{(x_1,x_2): 2x_1-x_2 \leq 0, x_1+3x_2 \leq 0\}$$
I am looking for a simple, illustrative, procedure to get its extreme rays.
Any suggestions?
My reasoning (if you have time)
I am…
k88074
- 1,661
- 8
- 18
7
votes
3 answers
How to formulate the constraint If $x = k$, then $y = c$?
Given are two integer variables $L_x \leq x \leq U_x$ and
$L_y \leq y \leq U_y$. I'd like to formulate the constraint
$$
\text{If} \;\; x = k, \;\; \text{ then } \;\; y = c,
$$
where $k$ and $c$ are given integer constants. Any help is highly…
hanhu
- 81
- 3
7
votes
2 answers
What strategies to use for Scheduling of Connected Sequences?
I'm given a problem in which I need to schedule multiple sequences. The goal is to minimize the makespan. I'm allowed to elongate all tasks, but I cannot reduce their width nor disconnect any of the tasks. Each of the tasks is indicated using a…
Barry S.
- 73
- 4
7
votes
2 answers
Is there a ranking of heuristics for the travelling salesman problem?
Does a ranking of TSP heuristics exist that is based on the quality of the solutions? For example a paper or another resource that compares the performance of TSP heuristics like the nearest neighbour, nearest insertion, saving algorithm,…
maxmitz
- 659
- 3
- 11
7
votes
1 answer
Bilinear programming vs Mixed integer linear programming performance comparison
I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, especially when all variables must have binary…
TUI lover
- 173
- 5
7
votes
1 answer
Branch and price with two sets of exponential variables
There are classes of problems which allow for "natural" extended formulations using multiple exponential-size sets of variables.
For example, 2-echelon routing problems can be modelled considering an exponential number of variables associated with…
Alberto Santini
- 2,113
- 9
- 23
7
votes
2 answers
Can QUBO solve this inverse Ising problem?
Inverse Ising Problem
The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins.
Each spin $s_{i}$ is either +1 or -1. The Hamiltonian of one configuration of spins $\vec{s}$…
Qurious Cube
- 523
- 2
- 7
7
votes
1 answer
Terrain Ruggedness Index for optimization problem
If I want to study the smoothness of the energy landscape of a cost function, is there any metric similar to Terrain Ruggedness Index used in geology?
Omar Shehab
- 251
- 1
- 3
7
votes
1 answer
Effect of 'unused' variables on the result and runtime of optimization algorithms
I have a general question about the effect of 'unused' variables on the result and runtime of optimization algorithms. I try to explain my question by giving an example. Let's say I have 2 type of buildings that I want to model. They have flexible…
PeterBe
- 1,632
- 2
- 15
- 30
7
votes
1 answer
Is there a real life application for the Bottleneck travelling salesman problem?
The bottleneck TSP tries to find a Hamiltonian circle which minimizes the longest edge. Is there any real world application for this for example in transportation?
maxmitz
- 659
- 3
- 11
7
votes
1 answer
Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?
The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "Lagrangian multipliers".
The sub-gradient algorithm…
Mehdi Iranpoor
- 79
- 2
7
votes
1 answer
How can I strengthen a family of constraints in the presence of a clique constraint?
Suppose $x_i$ are binary variables, $y_j$ are arbitrary variables, $a_j$ and $b$ are constants, and I have the following linear constraints:
\begin{align}
x_i + \sum_j a_j y_j &\le b &&\text{for all $i$} \tag1\\
\sum_i x_i &\le 1…
RobPratt
- 32,006
- 1
- 44
- 84
7
votes
2 answers
Logic-based Benders decomposition with integer master variables
I am looking for a paper/study in which a Logic-based Benders decomposition (LLBD) framework is used when the master problem is associated with integer variables (not specifically binary).
In general LBBD, we often send fixed binary solutions to the…
whitepanda
- 314
- 1
- 12