7
votes
In linear programming, is there a way to constrain two variables to not have opposite sign
I don't think it is possible in general.
If we introduce variables $t_i$, we can write the problem as:
$\max ...$
s.t.
$x_i \ge t_i$
$ y_i \ge 0 $
$ x_{min} \le t_i \le 0 $
$ y_it_i = 0 $ (this ...
- 1,785
5
votes
Accepted
Checking the feasibility of a system of inequalities
You can check feasibility of a set of linear inequalities by constructing a linear programming (LP) problem with a "dummy" objective, e.g.,
$$
\begin{align}
\max_{\{x_i\}_{i=1}^n} &\;0\\
\text {...
- 741
4
votes
Accepted
linear programming feasiblity checking
The short answer to your question is: kind of.
There are methods called "preprocessing" or "presolve", that will take a problem with constraints $b_{l} \leq Ax \leq b_{u}$ and $l \leq x \leq u$ as ...
- 30.4k
4
votes
Accepted
Largest hypercuboid inside a polyhedron
It turns out that the problem has quite an elegant solution.
Let the hypercuboid be defined by $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ instead of using the more cumbersome $\mathbf{x_{0}}$ and $\...
- 572
4
votes
Checking the feasibility of a system of inequalities
I agree with Stelios' answer, but it could use some fleshing out. This problem is called the "Phase One" problem.
First, convert your problem into "standard form".
\begin{align*}
\min_x 0 \\
s.t. \;\...
- 1,512
4
votes
Accepted
Determine image of hypercube under linear map
I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient ...
- 181
4
votes
Accepted
What is the name for this type of constraint?
I would call the constraint "upper- and lower-bounds on the maximum element." Note that you are actually dealing with two separate constraints. Define the
max element function as follows
$$
\max:\...
- 2,495
4
votes
Accepted
Solving a linear program with an active set method
Yes, it would be called the Simplex algorithm.
An active set method for solving Quadratic Programming problems is often called a "Simplex algorithm" (which is as opposed to an Interior Point method).
- 2,242
4
votes
Accepted
Linear system with an l1-norm constraint
The set of $x$ such that $|x_{1}| \geq \sum_{i=2}^{n} | x_{i} |$ is a non-convex set, but it's relatively easy to look for solutions where $x_{1} \geq \sum_{i=2}^{n} | x_{i} | $ and then look for ...
- 18.9k
3
votes
Find a solution of large system of inequalities
The goal is to compute an $x\in\mathbb{R}^{n}$ to satisfy the strict
inequalities
$$
f(z_{i})^{T}x>0\qquad\forall z_{i}\in\{1,\ldots,m\}.\tag{1}
$$
If we write $\epsilon>0$ as the smallest ...
- 2,495
3
votes
Getting Extremal Rays of Cone
You can use a randomized approach to solve this, as I mentioned in the comments. Ultimately, we have the equality constraint for our solution vector $\lambda$ being $A \lambda = \boldsymbol{0}$, for ...
- 4,308
3
votes
Is it more efficient to capture many constraints in one constraint?
I'd recommend setting each variable to 0, rather than trying to do something clever.
This is for two reasons:
You might be too clever and make a mistake. For instance, setting each variable to zero ...
- 4,021
3
votes
Is there a name for this integer linear optimization problem?
This is a minimum cost network flow problem. Construct the network as follows. You haven't specified the ranges for $i$ and $j$, but I'll assume that we $i=1, 2, \ldots, m$ and $j=1, 2, \ldots, n$.
...
- 18.9k
3
votes
Accepted
Linear programming with stochasticity?
There is a huge literature on "stochastic programming", but you're probably interested in what is called "chance constrained programming", in which the constraint coefficients are random variables, ...
- 18.9k
3
votes
Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?
You could split the original problem into two linear programming problems, the first with objective $f(x_1)=a_1 x_1 -a_2 x_1$ and (additional) constraint $x_1\geq 0$, and the second with objective $f(...
- 741
3
votes
Accepted
implied equalities and relative interior
Probably not the most efficient way, but you could do:
Formulate the system of inequalities as
$Ax - s = b$
$s \geq 0$
Then maximize $s_{i}$ with respect to the inequalities for $i=1, 2, \ldots, ...
- 18.9k
3
votes
Modeling a quadratic constraint with a linear expression
Suppose $$z_{i} = x_{i} \times y_{i}$$
The constraint $$ \sum_{i=1}^{n} x_{i}y_{i}\le 1 $$ can be reformulated as linear constraints:
1) $$ \sum_{i=1}^{n} z_{i}\le 1 $$
2) $$ z_{i}\le x_{i} $$
3) $$...
- 31
3
votes
What's the fastest software(open source) to solve mixed integer programming problem
I'd recommend SCIP or HiGHS (www.highs.dev). On the industry standard benchmarks (http://plato.asu.edu/bench.html) their relative performance is similar, but on specific classes of MIPs one may be ...
- 131
3
votes
Accepted
Maximum Constraints Satisfaction of Linear Programming
For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible ...
- 18.9k
3
votes
Python solvers for MINLP in Pyomo in Google Colab
There are so many MINLP solvers out there that this isn't really a well-defined question.
Anyway, here's how you can get some:
...
- 4,021
3
votes
In linear programming, is there a way to constrain two variables to not have opposite sign
When we "Plot" the region covered by a Pair of $(x,y)$ variables , we can see that it is Non-Convex , hence Linear Programming can not work out.
With that Point , we have couple of ...
- 141
3
votes
Accepted
In linear programming, how can I specify a lower bound for the positive entries in the decision vector
You have a disjunctive inequality which may be expressed as $[z=0,x \leq 0] \vee [z=1,x \geq 5]$. This is non-convex, so cannot be expressed as an LP. But as you suggest, there is a way to formulate ...
- 716
3
votes
Accepted
Solving linear system of equations with constraints on unknowns
I will use the notation $U_k$ and $U_{k,i}$ for rows and elements of matrix $U$, rather than small letter $u$, to avoid possible confusion with the $u_k$ notation in $y_k=au_k+bu_{k-1}+cu_{k−2}+pa^2u^...
- 716
2
votes
Perturbation in bounds given the perturbation to constraints
I assume that you're interested in
$b-\epsilon \leq a^{T}x \leq b +\epsilon$
rather than
$b+\epsilon \leq a^{T}x \leq b +\epsilon$
right?
If you're interested in more complicated ...
- 18.9k
2
votes
Literature on comparing Simplex and Interior-Point-Methods (or combining both of them)
I am not sure what you mean by comparing and combining. But a general textbook on linear and, more generally, convex optimization that I can recommend is the one by Stephen Boyd:
Boyd, Stephen, ...
- 51
2
votes
Accepted
From deterministic to stochastic LP formulations
(1.8) is a simple reformulation of the deterministic LP (1.2) It's still a deterministic LP. This may be somewhat confusing since the authors are going back forth between a deterministic LP ...
- 18.9k
2
votes
Accepted
What is a "good enough" method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?
(This answer is the work of Michal Forišek ... I will paraphrase here)
First reformulate the problem by nomalizing the constraints and weights yielding:
$\sum v_i = 1$
$\forall i: \min_i \leq v_i \...
- 151
2
votes
Ways to speed up solving an LP with Google's ortools
Have you tried any of the Coin-OR tools, like cbc or clp? They are pretty comparable to CPLEX for LP (not MIPs though), at least until a certain scale of the problem (your size should be solvable ...
- 21
2
votes
How to perform linear programming sensitivity analysis in MATLAB?
The fifth output from linprog are the dual variables, which you can use for sensitivity analysis.
- 1,848
Only top scored, non community-wiki answers of a minimum length are eligible