Questions tagged [linear-programming]
Referring to optimization problems that consist only of linear constraints and a linear objective function.
142
questions
1
vote
1
answer
195
views
Solving linear system of equations with constraints on unknowns
I would like to solve a system of linear equations $y=Uh$ for an unknown vector $h$, where I have a few constraints on some of the elements of $h$. The matrix $U$ is composed of a vector $u$ (length $...
- 35
2
votes
2
answers
108
views
Can this problem be solved using convex optimization?
I have the following problem:
$$\begin{align}
\max & \quad \frac{\mu^\top x - c^\top|x - x_0|}{x^{\top}\Sigma x} \tag{1} \\
\text{subject to }
& \quad x \leq \mathbb{1} \tag{2}\\
& \quad ...
- 23
1
vote
3
answers
287
views
In linear programming, how can I specify a lower bound for the positive entries in the decision vector
For decision vector $x$, I have a constraint that either $x\leq0$ or $x\geq5$, that is, all positive entries must be at least 5.
Is there a way to cast this under LP? The problem is already a mixed-...
- 482
0
votes
1
answer
91
views
MIP - Large Piecewise Linear Constraints Over Continuous Intervals
I'm currently trying to run a MIP (have access to both Gurobi and CBC) with a piecewise linear function having ~200 intervals for each of the ~30 x values I have. I am using the standard decomposition ...
6
votes
2
answers
1k
views
In linear programming, is there a way to constrain two variables to not have opposite sign
Say I have two sets of variables $x$ and $y$ of equal size. $x$'s have a lower bound $x_{min}<0$, and $y$'s have a lower bound $0$.
Is there a linear way to constrain that $x_i\geq0$ if the ...
- 482
1
vote
0
answers
33
views
Constraints involving max in ILP
Consider $n$ apps and $m$ transactions. $x_{ij}$ is a binary variable, it takes 0 or 1. $x_{ij}$ takes 1 if $i$th app is used for $j$th transaction, else 0.
min $\sum_{i=1}^{n}\sum_{j=1}^{m} x_{ij}$
...
- 111
0
votes
0
answers
57
views
Linear Programming with bounds on magnitude
I have a set of halfplanes $H$, and a target vector $T$. My goal is to find the vector $v$ closest (2-norm) to vector $T$, such that $v$ is in the intersection of all of the halfplanes.
This can be ...
3
votes
0
answers
84
views
When is it worth it to use the dual simplex method with warm starts?
Let's say I have a linear program that incurs a series of slight changes to it, so I want to warm-start it. I've read various things that recommend using the dual simplex algorithm over the primal ...
- 131
1
vote
0
answers
61
views
Package Assignment problem to maximize profit
Problem description
We have a graph $G=(V,E)$. $V$ is the set of nodes. $c_{ij}$ is the profit of traveling through edge $(i,j)$. $T=\{1,2,3,...\}$ is the set of discrete time steps.
At each time step,...
- 11
1
vote
0
answers
105
views
Using absolute error as the cost function
This is related to my previous post Minimize distance between curves.
I have a dataset with values of multiple curves. An example plot is shown below.
I want to scale the curves (move up/down) so that ...
- 433
2
votes
1
answer
103
views
How can we model time progress in linear programming?
I am trying to solve a scheduling problem with linear programming. I have N disks that each have a capacity of constant C. At each time interval t_i, a set of write requests with different sizes ...
2
votes
1
answer
158
views
Linearize problem with absolute value
Is there any method to linearize the following optimization problem?
\begin{align}
min_{x,y} &~~ c~[x; y] \\
st &~~ \sum x\leq \alpha_1 \\
&~~ \sum |y|\leq \alpha_2 \\
&~~ \sum y= 0 \\
...
- 121
2
votes
1
answer
2k
views
Python solvers for MINLP in Pyomo in Google Colab
I am looking for a MINLP solver that works with Pyomo models which can be used in the Google Colab environment. I have already found MindtPy but it doesn't work in google colab.
0
votes
0
answers
77
views
Equivalence between zero sum games and linear program
It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the ...
- 131
0
votes
1
answer
192
views
Maximum Constraints Satisfaction of Linear Programming
The question I need to solve is to maximize the satisfied constraints in linear programming.
To be more specific, Suppose I have an infeasible LP problem, my goal now, is to find the maximum number of ...
- 11
2
votes
0
answers
114
views
Model and solve nutrition optimization problem: how to?
How to solve/assess the following problem?
Given: $N$ ingredients like apples, bread etc. Mass of an ingredient $j$ is in this simplified model a sum of macro nutrients carbohydrates, proteins and ...
- 193
6
votes
1
answer
223
views
Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$
I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
- 63
0
votes
0
answers
81
views
Balanced constraint
In several optimization problems, we found what we called the balanced constraint(c^T • x = z )
For exp: C^T • 1 = 0 (C is a binary Matrix)
Can I have an intuitive explanation about the concept and ...
- 31
1
vote
1
answer
280
views
Linear system with an l1-norm constraint
I have a saddle-point system of the form
\begin{equation}
\begin{bmatrix}
A & B \\
B^T & O
\end{bmatrix}\begin{bmatrix}
x\\
y
\end{bmatrix} = \begin{bmatrix}
f \\ \vec{0}
\end{bmatrix},
\end{...
- 143
1
vote
1
answer
519
views
Solving a linear program with an active set method
Is it possible to solve a linear program with an active set method? If so what would be the similarities and differences to the simplex method?
- 13
2
votes
2
answers
126
views
Using MILP to place a set of primers along a genome
Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$.
Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located).
Let ...
- 503
0
votes
0
answers
50
views
Optimizing vectors with equal elements
I am trying to distribute power across different devices, so that the sum is as equal as possible to the power setpoint. At the same time, the sum of power per phase must not exceed the power of the ...
- 1
1
vote
0
answers
109
views
Fastest way to solve linear programming with 6 complex inequalities and 5 nonnegative variables
I have a program where I need to solve a linear programming problem in a fast loop. The language I'm using is Java and any kind of bindings to other languages are not acceptable. Libraries might be ...
- 151
0
votes
0
answers
96
views
Are there unproblematic max constraints when modelling problems as Linear Programs?
Suppose we have a linear objective function that we want to maximize.
All variables are from the set of reals.
We have a constraint of the form:
$$\max(x_1,x_2) + \max(x_3,x_4)\leq c\,, \text{ with } ...
- 1
2
votes
0
answers
77
views
Interior point of convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
- 146
-1
votes
1
answer
59
views
FORM by NIKHEF: unexpected behavior wrt summation
I have two almost identical FORM (by NIKHEF) scripts here:
script_1
script_2
which differ only in summation at the end. In first case the summation in done in one step, in the second case ...
- 115
3
votes
0
answers
81
views
Hit-n-Run Monte Carlo on convex polytope
So, I'm currently trying to implement a MCMC to uniformly sampling hyper-points from the polytope defined as $\mathbb{K}=\{x\in\mathbb{R}^{n}\;\;\text{s.t.}\;\; A\,x=b \}$ in the specific case where, ...
- 146
1
vote
0
answers
41
views
Long AMPL model preparation time
We deal with a large-scale linear optimization problem (~50000 variables and ~4000000 constraints). We use AMPL Studio modeling environment for problem modeling and then calling linear solver (CPLEX, ...
2
votes
1
answer
165
views
Getting Extremal Rays of Cone
So I have a set of linear homogeneous equations $A\vec{x}=0$. I would like to solve this for non-negative solutions. I can solve the system in general and I get the two vectors that span the solution ...
user32362
2
votes
1
answer
276
views
Is it more efficient to capture many constraints in one constraint?
I have a number of variables that need to be set to 0. They are positive real numbers so the way I see it I can do this by setting each one to 0 by separate constraints, or I can set their sum to zero....
- 29
1
vote
1
answer
88
views
Is there a name for this integer linear optimization problem?
I have an integer linear programming problem of the form:
$$\DeclareMathOperator{\tr}{tr} \min \tr WX$$ subject to:
$$\begin{align}
\sum_j X_{ij} < c_i && \forall i \\
\sum_i X_{ij} = 1 &...
- 359
4
votes
1
answer
62
views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
- 181
2
votes
3
answers
1k
views
Find a solution of large system of inequalities
I have a large system of homogenous inequalities involving 33 real unknowns of the form
$$
\vec{F}(z_i)^T \cdot \vec{X}>0\,
$$
where $\vec{X} = \left(x_1,...,x_{24}\right)^T$ are the unknowns and ...
- 159
5
votes
1
answer
123
views
What is the name for this type of constraint?
I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take ...
3
votes
0
answers
119
views
Solving multiple linear programs with same constraints but different objective
I have ~30 non-negative variables and 24 equations and I want to find out the upper and lower bound for each variable. Feasible solutions are guaranteed.
So for each variable, I solve two LP problem, ...
- 482
2
votes
0
answers
119
views
Where can I find sample data for large linear programming optimization problems?
I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
1
answer
308
views
Splittable and non-splittable flows in the network flow problem
I am working on a multi-commodity flow problem where for a graph $G=(V, E)$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as ...
- 13
3
votes
1
answer
97
views
What is a "good enough" method of assigning values to n variables subject to basic bounding constraints while maintaining relative weights?
Given triples of $n$ floating point values
$$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$
and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that ...
- 151
2
votes
0
answers
78
views
Weighted Set Cover in practice, beyond the greedy algorithm
According to the wikipedia page for Set Cover, the greedy algorithm for weighted set cover achieves the polynomial-time approximation bound. There are other techniques for solving Set Cover, such as ...
- 251
2
votes
0
answers
57
views
Transforming an arbitrary linear program into one with an interior point
Primal-dual interior point methods for linear programming require interior primal and dual starting points. I am looking for a good reference containing a description for modifying a given linear ...
- 11.4k
7
votes
1
answer
3k
views
Ways to speed up solving an LP with Google's ortools
I'm having an issue solving an LP of the form:
$$\min z = c^Tx$$
$$\text{s.t.}$$
$$Ax \geq b$$
$$x\geq p$$
$1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$
The specific problems I'm running into ...
- 171
2
votes
0
answers
382
views
Finding integer/lattice points (coordinates) inside a polytope/polyhedra?
I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that ...
- 121
1
vote
2
answers
90
views
implied equalities and relative interior
What is the best method to find for a linear system of inequalities $Ax\ge b$ with dense $A$ of moderate dimension the affine subspace spanned by the feasible points (i.e., the implied equalities $(Ax)...
- 11.4k
4
votes
1
answer
535
views
Why do active set methods or the simplex method pivot only one variable at a time?
Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
- 767
1
vote
1
answer
2k
views
Solve a set of multivariate linear inequalities with constraints in Python
I'm trying to implement Dinur-Nissim algorithm and am stuck at how to solve the set of linear inequalities with multiple unknowns and a large number of equations along with constraints.
Example:
\...
- 11
0
votes
1
answer
879
views
How to perform linear programming sensitivity analysis in MATLAB?
I would like to perform post-optimal analysis using Matlab linprog. But it does not provide any information about that. So required a way to get the info about optimal basis, basic and non-basic ...
3
votes
1
answer
68
views
Linear programming with stochasticity?
Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution.
Now, I would like to solve the same problem but with stochasticity ...
- 133
1
vote
3
answers
174
views
Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?
I have an optimization problem that I'm trying to cast as a linear program. However, I have an objective function of the form
$$\begin{array}{ll} \text{maximize} & a_1 x_1 - a_2 \lvert x_1\rvert\\...
- 123
5
votes
1
answer
220
views
Largest hypercuboid inside a polyhedron
Given a polyhedron $\mathbf{Ax} \leq \mathbf{b}$, how to find the largest hypercuboid, with unknown center $\mathbf{x_{0}}$ and side lengths $2\epsilon_{i}$, which are aligned along the co-ordinate ...
- 572
4
votes
3
answers
4k
views
Checking the feasibility of a system of inequalities
I have $m$ inequalities involving $n$ variables as follows
$$a_{1,j} x_1 +a_{2,j} x_2 +\dots +a_{n,j} x_n>0 \quad \text{for} \quad 1 \leq j \leq m$$
How can I check if a solution exists (with the ...
- 143