New answers tagged linear-programming
3
votes
Accepted
Formulation of binary constraint with the least binary variables for linear programming
You want to impose the following two logical constraints:
$$
\begin{align}
\delta_{t-1} = 1 \wedge \delta_t = 0 &\implies \beta_t = 1 \tag{1} \\
\neg (\delta_{t-1} = 1 \wedge \delta_t = 0) &\...
- 1,477
1
vote
Accepted
how do I find the dual when a variable has an upper bound?
You can imagine the upper bound for the variable is another constraint.
$\max: c^Tx$
$\text{s.t.}$
$Ax = 0$ --> $π_1$
$x ≤ d$ --> $π_2$
$0 ≤ x$
Therefore, you will obtain the following dual form....
- 101
1
vote
How to select intermediate nodes in a network?
Option 1: Run Dijkstra's algorithm first. Then you will have a grid of positive numbers that you can use for additional constraints. E.g. require a positive number to know that a path is available ...
- 837
3
votes
Accepted
Optimization Problem with a Penalty Factor
You have two separate objectives: maximizing terminal value $A$ and minimizing (or at least reducing) initial investment $P.$ You might want to search the web using the phrases "bicriterion ...
- 37.4k
2
votes
Linearizing if else conditions in ILP
Besides @RobPratt's answer, the first condition would be (for simplicity I omitted indices $i$ and $j$ and continued with only two $y$ variables:
$$ x \implies (y_1 \oplus y_2) $$
$$ \lnot x \lor (y_1 ...
- 8,165
2
votes
Accepted
Linearizing if else conditions in ILP
Your first constraint enforces more than was asked. When $X_{ij}=0$, it forces $\sum_k Y_{jk}=0$, hence $Y_{jk}=0$ for all $k$. To enforce only $$X_{ij}=1 \implies \sum_k Y_{jk}=1,$$ you can instead ...
- 29.7k
5
votes
For an ILP relaxed to LP is the LP solution objective always less than the ILP solution?
If the integer linear programming is a minimization problem then whose linear relaxation is a lower bound for the original MILP model, and for the maximization problem it is an upper bound. In the ...
- 8,165
5
votes
Which solvers should I use to solve large, but extremely sparse LP problems with 100-500 thousand variables?
Based on the Mittelmann benchmarks, I would agree that HiGHS is a contender, as is Clp (which is faster than HiGHS on some test problems, slower on others). You might also want to look at SCIP, which ...
- 37.4k
7
votes
Accepted
Which solvers should I use to solve large, but extremely sparse LP problems with 100-500 thousand variables?
One of the best-performing free LP solvers exploiting sparsity is HiGHS (https://github.com/ERGO-Code/HiGHS). It allows passing a starting point.
For comparing relative performance of a number of LP ...
- 2,856
4
votes
How to handle strict inequalities?
In practice, most solvers are implemented to use fast but inexact floating-point arithmetic and thus can only ever guarantee to satisfying the optimality conditions of your problem to within some ...
- 1,337
2
votes
How to handle strict inequalities?
I'm not aware of a special name for those kind of problems. In order to solve it in practice, you might add a small constant numerical tolerance $\varepsilon > 0$, e.g. $\varepsilon = 10^{-8}$, and ...
- 1,477
1
vote
Accepted
Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat
You'd need two optimization variables
Binary $ x_{s,r} = 1$ if student $s$ from set A is matched with row $r$ from set B
Binary $ y_{s,c} = 1$ of student is matched to a class $c$
Derived sets/matrix ...
- 3,300
0
votes
Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat
create 1 Boolean var per pair of (student, course)
Write the linear equations that constrain the model
Decide on the objective
- 2,558
Top 50 recent answers are included