The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
57 views

Find base of kernel with as many 0 as possible

I have a 400x132 rectangular matrix with only 0 and 1. I am looking for the linear combinations of the columns of the matrix that sum to 0. For example C1 + C2 - C3 = 0. I want to find the linear ...
2
votes
2answers
97 views

Boundedness of ratio of linear functions

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
0answers
55 views

polynomial 0,1 integer programming

IS there a mathematical optimization branch that explicitly tries to optimize this (type) problem? $$\eqalign{ & \min \cr & \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + ...
0
votes
1answer
70 views

Solution of infinite dimension linear system

Suppose that ${a_n}$ and $b_n$ is decreasing sequence such that $a_0=A$, $lim_{n->\infty}a_n=0$ and $b_0=B$, $lim_{n->\infty}b_n=0$. For fix n, we can construct n dimension linear equation ...
2
votes
2answers
233 views

convex polytope integer points

is there a simple proof for the following lemma: An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
0
votes
2answers
58 views

Approximate solution to large mixed integer programming problem

What are the available approaches to find an approximate solution to a large mixed integer programming problem? I ran my problem in the Gurobi MIP solver. It can find a feasible solution in ...
1
vote
1answer
80 views

a closed form lower bound solution for linear programming

Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it? to clearly express the problem assume that $$ z(\mathbf{a,B,c})=\mathop {\inf} ...
1
vote
1answer
115 views

Name search for special Linear Integer Program

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
2
votes
1answer
140 views

Optimization problem whose cardinality never exceeds 7 for some reason

I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
1
vote
1answer
123 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
2
votes
0answers
52 views

Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings

In one paper from 1980 I found a note that there are no known algorithms for solving homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring. (The ...
1
vote
2answers
47 views

Linear Programm with matrix [closed]

Is there a name for problems like this min norm(Cx) Ax = b where C is a matrix and norm is the maximum norm. This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
0
votes
0answers
45 views

integrality of a linear program — binary equality constaints

Consider the following linear program: $\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$ where $c$ is a vector ...
1
vote
0answers
43 views

Maximize minimum optimization using linear integer programming [closed]

I am trying to solve a maximize minimum optimization. I have four different items that each of them has 10 values of Rates and for each value it has a corresponding weight. Then I have a free table ...
4
votes
2answers
120 views

combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual ...
1
vote
0answers
52 views

Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints? ...
0
votes
0answers
43 views

Multi-objective set-cover optimisation problem

I'm looking for an algorithm to solve the following multi-objective set-cover problem. We start with a 'universe' (set) of items $\mathcal{U}$, along with a partitioning $P = \{p_0,\ldots,p_m\}$ ...
1
vote
1answer
181 views

Maximizing linear objective function with absolute values

This has be asked on other forums, though couldn't find authoritative answer. I have a linear program over the reals and don't want to introduce integer or binary variables. The objective function ...
2
votes
2answers
128 views

Finding the maximum of a multivariate polynomial of degree one

I need to find the global maximum of the function \begin{align} f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\ &+\ldots \\ &+ p_n ...
1
vote
0answers
96 views

Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint: ...
0
votes
1answer
47 views

generalization from linear programming solution [closed]

I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
6
votes
1answer
237 views

Has this generalization of a determinant (assigning multiplicities to the rows) been studied?

I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant: Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
1
vote
1answer
145 views

Minimizing sum of absolute deviations

Suppose we want to find coefficients $b$ in $\underset{b}{\operatorname{argmin}} \displaystyle\sum\limits_{i=1}^n | y_{i}-b_{1}x_{i}-b_{0}\mid$. If we rewrite this problem in terms of linear ...
20
votes
4answers
1k views

Why are optimization problems called “programming”?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
4
votes
2answers
364 views

Simplified knapsack problem

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
2
votes
1answer
142 views

For interior point methods of linear programming, what is the “L” in the computational complexity $\mathcal{O}(n^3 L)$?

My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
1
vote
0answers
78 views

Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method

I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
4
votes
2answers
199 views

point in polytope

Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
2
votes
1answer
284 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
127 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 ...
3
votes
1answer
151 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
25 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 ...
2
votes
0answers
122 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
206 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
114 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
172 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) = ( ...
2
votes
2answers
94 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
453 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 ...
2
votes
0answers
39 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$, ...
2
votes
0answers
68 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
1answer
340 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
2answers
342 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
111 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
541 views

Robust optimization in matlab using fmincon [closed]

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
305 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 ...
10
votes
2answers
747 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 ...
2
votes
0answers
127 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 ...
5
votes
2answers
254 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
54 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 ...
-1
votes
1answer
2k views

If then condition on mixed linear integer programming [closed]

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 < ...