Most Popular
1500 questions
7
votes
3 answers
Binary logical constraint dependent on indices
I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.
I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to represent that,
if $X_t=X_{t-1}$ then…
orpanter
- 517
- 3
- 10
7
votes
1 answer
How can one model a binary variable?
I am looking for the formulation of a constraint that does the following. I want to introduce a new binary variable $\kappa_{it}$ that takes the value 1 if the sum of the other binary variable $\omega_{it}$ is greater than or equal to the number…
nflgreaternba
- 99
- 1
- 8
7
votes
2 answers
Will there be Rust APIs for state-of-the-art solvers?
The Rust programming language is gaining popularity. As the title says, I wonder if state-of-the-art, say MILP, solvers will eventually release APIs for the Rust programming language. Solvers such as Cplex and Gurobi have APIs for some of the most…
k88074
- 1,661
- 8
- 18
7
votes
0 answers
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that the graph is, or is not, planar.
The python…
Kuifje
- 13,324
- 1
- 23
- 56
7
votes
2 answers
Traffic lights optimization
I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below:
The goal is maximize the duration during which each movement $m\in M=\{a,...,j\}$ has a green light, subject to the…
Kuifje
- 13,324
- 1
- 23
- 56
7
votes
1 answer
How to interpret the random solution pick by Lévy flight on cuckoo search
I am working on an implementation of Cuckoo Search for a set covering problem. After reading some papers I cannot understand how choosing a random solution (new cuckoo) works. What I see is that solutions are represented in 2 dimensions and by Lévy…
Cristofer Fuentes
- 181
- 4
6
votes
3 answers
How do we formulate a problem where the decision variable has an index that is also a decision variable?
I want to maximize the sum of a nonlinear function $f(.)$ w.r.t. $x$ that is convex in $x$:
$$\max \sum_{i=1}^N f(x_i), $$where $x_i$ is a continuous variable and $0 \le x_i < 1$ for $i = 1, 2, \dots , N$.
But in this problem, $x_i$ is restricted to…
Steven01123581321
- 1,043
- 6
- 12
6
votes
2 answers
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 define uncertainty of the parameters by defining…
Pia MiA
- 392
- 1
- 10
6
votes
2 answers
How to partition a giant tour into feasible routes?
In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then transforms this tour into smaller feasible ones (see for example…
Kuifje
- 13,324
- 1
- 23
- 56
6
votes
2 answers
Is this constraint with an indicator function nonlinear?
We have two variables $x\geq0$ and $y\in\mathbb{Z}^{0+}$.
We have this constraint in our model
$$x = \sum_{i = 0}c_i \mathbb{1}_{\{y=i\}}$$
where $c_i$ is a parameter and $\mathbb{1}_{A} = 1$ if $A$ is true and zero otherwise.
Is this constraint…
user10774
6
votes
2 answers
Cover cuts for knapsack constraint with integer variables
It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover cuts are $\sum_{j \in C} x_j \leq |C| - 1,…
CHE
- 113
- 7
6
votes
1 answer
Is it possible to express these constraints with basic cones?
I have the following optimization problem:
\begin{align}\min&\quad x\\
\text{s.t.}&\quad x=\max_{i} \{x_{i}\}\\
&\quad x_{i}y_{i}=z_{i}\\
&\quad x_{i}, y_{i}, z_{i}\geqslant0
\end{align}
with $i\in\{1,\ldots,n\}, n \in \mathbb{N}$ and some linear…
PNoug
- 61
- 1
6
votes
1 answer
Doubles Round Robin Sorting Algorithm
Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, each player plays 4 games, and sits for 2 games. …
WoodGuyPurdue
- 63
- 3
6
votes
2 answers
Breaking symmetry of permutations in LIP
Setup
I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using this two-dimensionality, but I can change this if…
armset
- 73
- 4
6
votes
4 answers
Constrained optimization of a sum
I have to maximize the function $f= \sum_{i=1}^na_ix_i $ subject to the constraints $g = \sum_{i=1}^n x_i = 0 $, $-1\leq x_i \leq 1$ and $a_i>0$. Lagrange multiplier method doesn't work because $\nabla f=\lambda\nabla g$ only yields $\lambda=a_i$…
Deep
- 163
- 4