The linear-programming tag has no wiki summary.
1
vote
1answer
99 views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
1
vote
0answers
53 views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
2
votes
1answer
60 views
Explicit formula for an LMI solution
Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):
$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$
(The notation $X \succeq Y$ means that ...
2
votes
0answers
19 views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
0
votes
0answers
40 views
Optimization with differential inequality constraint
Consider the closed set $[t_1,t_2]⊂R_{>0}$ and $V(t):[t1,t2]→R_{>0}$ being a continuous and piecewise continuously differentiable function. We want to find a continuously differentiable function ...
2
votes
0answers
78 views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
2
votes
1answer
61 views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
0
votes
2answers
96 views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
1
vote
2answers
165 views
Name of operations on two vectors
Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...
1
vote
2answers
61 views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
0
votes
1answer
112 views
What does “Vertex Solution” mean?
Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...
0
votes
0answers
66 views
Uniqueness result
For a standard linear programming problem, let $V$ be a real Hilbert space, $v\in V$ being fixed. $C$ a convex subset of $V$. What is the condition we have to impose on $u$ and $C$, so that the ...
2
votes
0answers
36 views
Put positive polynomial in finite intersection of half-spaces
This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...
1
vote
0answers
54 views
Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?
In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...
1
vote
0answers
156 views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
0
votes
0answers
141 views
If-then-else on mixed linear integer programming
Hi all.
Let A,B and C be three real variables. I must write the following if-then-else condition with linear inequalities:
if A≤B then C=0 else C=B-A
Is this possible by adding a single binary ...
0
votes
2answers
170 views
Efficient algorithm finding 'a' solution of system of linear inequalities
I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...
1
vote
2answers
89 views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
1
vote
0answers
252 views
Robust optimization in matlab using fmincon [on hold]
I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...
0
votes
1answer
140 views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
8
votes
3answers
546 views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
1
vote
0answers
88 views
How to implement linear constraints that include several absolute values
Dear all,
I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1
Since the minimization problem includes quite a ...
0
votes
0answers
49 views
Finding dual feasible solution from primal feasible solution
Hi
I would appreciate if I could find the answer of this question:
I have a primal problem and by using heuristics I was able to generate feasible solution. Would please give me an idea how can I find ...
0
votes
0answers
29 views
minimization extension on l_1 trend filtering
I am trying to solve the following problem presented in the extensions section of Stephen Boyd's l_1 Trend Filtering paper. I have had relatively zero luck getting this problem to work out correctly. ...
5
votes
1answer
181 views
relation between solution of a linear program and its perturbation
I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:
$$
\max_j c' x_j
$$
Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
0
votes
0answers
45 views
Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?
I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise.
The other variables in the linear ...
0
votes
1answer
543 views
If then condition on mixed linear integer programming
Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities:
if $a < ...
0
votes
0answers
134 views
A linear program related question
Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, ...
0
votes
1answer
86 views
Cascading minimization problems
Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. ...
0
votes
2answers
217 views
linear programming with OR restrictions
Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is:
minimize: $w^Tx$
subject to: $Ax=b$, $Cx \le d$ and for ...
0
votes
2answers
341 views
Find both maximum and minimum values in linear programming problem
Hi all. I have a linear programming problem where I need to find both maximum and minimum values of the objective function. The optimal points are not relevant.
Is there an efficient way to do so?
0
votes
0answers
136 views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0answers
127 views
$\ell_o$ Minimization (Minimizing the support of a vector)
I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
1
vote
2answers
170 views
what method can I employ to solve this optimization problem which involves \min?
The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N ...
1
vote
0answers
120 views
Consistency of a system of linear equations
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
1
vote
0answers
182 views
Totally Uni-modular Matrices
A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
0
votes
0answers
63 views
computing centerpoint using linear programming
Hi
I am a student trying to teach myself discrete geometry with books such as Matousek and others. I am starting with the centerpoint problem and reading some literature. I want to know if someone ...
0
votes
1answer
93 views
Continuity of Lexicographic Minimum Solution of a parametrized LP problem
Given a parametrized LP problem
find x, that minimizes F*x
such that Ax <=Bt+D
where t is a parameter.
And suppose C(t) is a set of all optimal solutions of LP with parameter t.
Let x_L(t) be ...
2
votes
1answer
228 views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
0
votes
0answers
105 views
find optimal solution from muliple sets of values
hi,
i am not too good with linear programming (or for that matter with mathematics). i am facing a problem at my work place. I have a job which can be processed on two machines (bw & kmc). The ...
0
votes
1answer
132 views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
0
votes
1answer
209 views
Sherali-Adams relaxation
I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
4
votes
1answer
185 views
Checking if one polytope is contained in another
Hi,
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
2
votes
1answer
101 views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
2
votes
2answers
312 views
how to model a linear program with step-like cost function in the objective
I have a large linear program with the following details.
d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form
d1 < d3 < d7 < d23 ...
4
votes
2answers
515 views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
2
votes
0answers
291 views
0,1 solution to system of linear integer equations.
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
1
vote
0answers
107 views
Computational complexity of state of the art in linear and quadratic programming
I'm trying to find out what is the current progress in solving LP and QP with non-integer variables.
I'm interested in cone / semidefinite programs particularly, because they are widely used, but it ...
7
votes
1answer
256 views
Does the Hirsch conjecture hold for $n < 2d$?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
2
votes
2answers
810 views
Solving a system of equations/inequalities that have trigonometric functions on the left-hand side
Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
