Most Popular
1500 questions
6
votes
2 answers
Heuristic solution to the graph partitioning problem
I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups?
But I need some MILP solver to solve this problem. I want a pure heuristic approach to…
KGM
- 2,265
- 7
- 23
6
votes
2 answers
If $t\le0$ then $P=1$, if $t > 0$ then $P =0$ or $P=1$
I am trying to model $t \leq 0.0 \implies P = 1.0$ else $P=1$ or $P=0$ where $0 \leq t \leq H$ is a bounded nonnegative real, and $P$ is binary.
I can use the expression $t + \epsilon P \ge \epsilon$ which however does not do the job when $0 < t <…
Clement
- 2,252
- 7
- 13
6
votes
2 answers
Linearise $\max\{ y_{t-1} + a_t - z_t ,0\}$
I'm trying to linearise these constraints, but I am not able to do correctly do it.
$$y_t = \max\{ y_{t-1} + a_t - z_t, 0 \} $$
My attempt was this:
\begin{align}y'_t &\geq a_t - z_t\\y'_t &\geq y^{'}_{t-1} + a_t - z_t \end{align}
Am I…
user4387
6
votes
1 answer
Why does CPLEX continue solving after finding the optimal solution?
I ran a MIP model with a max solving time of 1800 seconds. CPLEX found the optimal solution (0.00 % MIP gap) after 710 seconds, but continued processing until it was stopped by the 1800 second limit.
When CPLEX already found the optimal solution…
Christian
- 217
- 1
- 4
6
votes
1 answer
Upper and lower bounds of a variable equal
I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex.
In order to easily exclude some variables from my problem I thought about setting both their lower and upper bound equal to '0.0'.
Now I have these…
rainbow
- 307
- 1
- 7
6
votes
1 answer
Can we remove symmetry from polytopes for analyzing them?
Consider the boolean quadric polytope, which is defined on a complete graph $G=(V,E)$ as:
$$QP = \{(x,z) \in \{0,1\}^{V+E} : x_ix_j=z_{ij} \}$$
Now we can generate for small examples with tools like porta, polymake the complete linear description.…
user3680510
- 3,655
- 6
- 26
6
votes
1 answer
MILP - stronger models
Let $y, x_1, x_2, x_3$ be binary variables.
The following holds: $y=1 \implies x_1=1, x_2=1, x_3=1$
I can model this by requiring (1) \begin{align}x_1 &\ge y\\x_2 &\ge y\\x_3 &\ge y\end{align}
or by requiring (2) $$\frac{x_1 + x_2 + x_3}3 \ge…
Clement
- 2,252
- 7
- 13
6
votes
1 answer
Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only
I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure of it. I know that (QCQP) has the following…
Ibrahim Amer
- 245
- 1
- 6
6
votes
1 answer
Why is the Bellman-Ford's shortest path algorithm sometimes called Bellman-Kalaba?
I see here and there, mostly in operations research courses in France that the Bellman-Ford algorithm related to shortest paths is called the Bellman-Kalaba algorithm. Could you explain the reason why it is called like that?
I searched and found a…
JKHA
- 679
- 4
- 10
6
votes
1 answer
Solver Recommendation : Discrete Variables and Quadratic Constraints
I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is linear.
I think this kind of problem is called…
Shinra_SGr
- 75
- 2
6
votes
0 answers
Water quality component optimization
I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain it clearly.
The objective is for Final1 node to…
Nisith Singh
- 61
- 3
6
votes
1 answer
Two equivalent soft constraint implementations
Take the following optimization problem:
\begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g(x)\le0\end{align}
with $f$ and $g$ nonlinear functions. Suppose I want to relax the constraint by replacing it with a penalty term proportional to the…
MDescamps
- 71
- 3
6
votes
2 answers
Forbid transformation of max(x,y) into MILP
The function $\max(x,y)$ can be linearized by making use of additional binary variables. I suppose global optimisers are implemented to perform this transformation automatically.
Is there a global optimiser that allows this function to be treated as…
Clement
- 2,252
- 7
- 13
6
votes
0 answers
Characterization for total dual integrality
A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the unimodularity of $A$ is a sufficient condition, which…
Surpass2019
- 137
- 3
6
votes
2 answers
Subtour elimination constraint in Travelling Salesman Problem
I am trying to understand travelling salesman problem, the Dantzig, Fulkerson, Johnson(1954) formulation. In the general formulation given below I am having trouble to implement subtour elimination in a practical problem.
$Min $$\sum\sum…
user5245