Most Popular
1500 questions
6
votes
1 answer
How to treat a system of bilinear constraints
A model contains constraints of the following form
$R(k) \leq X(k) G(k)$
where $X(k)$ binary and $G(k)$, $R(k)$ non-negative variables.
The index $k$ runs from $1$ to $50$.
I linearise the equations as they are products of binary and continuous…
Clement
- 2,252
- 7
- 13
6
votes
2 answers
0 1 solution of linear programming problem with only equality constraints
I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that is each constraint is the sum of three distinct…
Mario Giambarioli
- 203
- 2
- 8
6
votes
3 answers
How does a solver generally know whether a solution is optimal?
I was wondering how does the solver for a MILP determine whether a solution is optimal. I am having a hard time to believe that the solver actually tries all solutions, since in some cases I have over 100 variables and a significant amount of…
Snowflake
- 517
- 3
- 9
6
votes
1 answer
What underlies intlinprog in MATLAB?
When a paper says they used the intlinprog in MATLAB to solve an integer program, what system actually does the solving? I have seen documentation about Gurobi and MATLAB: does Gurobi always provide the solving for MATLAB or is that just one…
Michael Trick
- 2,362
- 9
- 34
6
votes
3 answers
Is a mathematical programming problem with no objective function an optimization problem?
I have a "mathematical programming" (MP) problem that does not have an objective function. Namely, I want to find a vector that satisfies all constraints (no optimization involved, right?). Now, a couple of (maybe) silly questions come to my…
jesús garcía
- 91
- 1
- 4
6
votes
2 answers
How to transform this logical if-then constraint?
Consider the binary variables $x, y, z \in \{0,1\}$.
I'd like to formulate the two if-then constraints:
$$ x + y \geq 2 \implies z = 0, \tag{1} $$
$$ x + y \leq 1 \implies z = 1. \tag{2} $$
Constraint (1) can be formulated as
$$
x + y \leq 2 -…
Ronaldinho
- 385
- 2
- 5
6
votes
1 answer
ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied
Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $x_i$'s. Consider an ILP constraint $x_1 + x_2 + x_3 \geq 1$ and another constraint $x_4 + x_5 + x_6 \geq 1$. I would like to represent that exactly one such constraint is…
ephemeral
- 897
- 4
- 12
6
votes
2 answers
What are some "clustering" algorithms? (but not the type of clustering you're thinking about)
Given a set of $N$ points $\{x\mid x \in \mathbb{R}^D\}$ for some dimensionality $D$ I want a fast algorithm which will give me all unique subsets which satisfy:
$\|x_{i} - x_{j}\|_{D} \leq M$ (all pairs of points in the subset are close to one…
Alexander Soare
- 433
- 3
- 8
6
votes
3 answers
How to validate a Gurobi academic license remotely via ssh SOCKS proxy?
How do I validate my Gurobi academic license remotely, that is, from a computer that is not on my university network?
Official instructions for Gurobi 9.1 are here: https://www.gurobi.com/documentation/9.1/quickstart_mac/academic_validation.html,…
Neal Young
- 169
- 7
6
votes
1 answer
Are there strategies/rules/systematic approaches to derive alternative formulations for an optimization problem?
For a given optimization problem there are often many known math programming formulations.
For example for the TSP here is a survey https://link.springer.com/chapter/10.1007/3-540-36626-1_5
of many different formulations, that all describe the same…
user3680510
- 3,655
- 6
- 26
6
votes
0 answers
What are useful plots/statistics/metrics when analyzing the solution sensitivity in multi-objective optimization?
Consider an optimization problem with $n>3$ objectives.
For handling this there exists often two approaches:
a) some weighting of the objectives,
b) fix an order of objectives and then optimize each one after another, allowing the objective of the…
user3680510
- 3,655
- 6
- 26
6
votes
3 answers
How do you take into account order in linear programming?
How do you write order in a linear program?
For instance, you want to arrange red and blue marbles labelled 1 – 30 each, and you would want to arrange it in ascending order, you cannot have red marble #28 before #7 - how do you communicate that…
wakwak
- 61
- 2
6
votes
2 answers
Directly calling gurobipy API causes substantially longer runtime than calling cvxpy
Background
I am trying to implement the reranking algorithm proposed in the paper (Eqn 3). The algorithm is cast into an integer linear program which is trying to find permutation matrix $\mathbf{X} \in \mathbb{R}^{n\times n}$, where…
Mr.Robot
- 171
- 4
6
votes
1 answer
Extreme point and extreme ray of a network flow problem
"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) in the network." I see this statement everywhere but…
Pramesh Kumar
- 411
- 3
- 9
6
votes
1 answer
OR-TOOLS : is it possible to partially fulfill a demand?
I am working on a vehicle routing problem with or-tools.
Is it possible to partially fulfill a demand? I know it is possible to drop nodes with the disjunction constraints. But in this case, a node is either visited, or not. I would like to allow a…
Kuifje
- 13,324
- 1
- 23
- 56