Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.

0
votes
1answer
58 views

sparse data fitting problem

I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?) Given a sparse data fitting problem: $ minimize \...
5
votes
1answer
176 views

Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?

Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent: The all-one vector $j$ is contained in the conic hull of $col(A)$. ...
1
vote
0answers
22 views

Supremum of expectations over a family distributions close to a base distribution

Let $p$ be a probability distribution on a space $X$ , $f:X \rightarrow \mathbb R_+$ be a measureable function, and $0 < \alpha \le 1 \le \beta < \infty$. Define a sub-collection $\mathcal Q \...
1
vote
0answers
25 views

How to minimize n-polytope's bounding box with linear transformation?

I am working on an exact algorithm for integer linear programming for my master's thesis: $Ax\leq b, x \in \mathbb{Z}^n$ $cx\rightarrow min$ For my idea to work out, I need a guarantee that n-...
0
votes
0answers
62 views

Are there efficient algorithms for transforming integer systems of linear equations with positive variables to inequalities and vice versa?

I have a problem in the form of a system of linear equations: Given $A \in \mathbb{Z}^{m \times n}$ and $b \in \mathbb{Z}^m$, find $x \in \mathbb{Z}^n$ satisfying $Ax=b$, $x \geq 0$. I want to ...
5
votes
1answer
104 views

Solving system of bilinear equations

Consider a collection of $m$ matrices $A_i$ of size $n\times n$, and a vector $b$ of size $m$. I want to solve the bilinear system $\{x^T A_i y=b_i:i=1,\dots,m\}$ in variables $x,y$. Is there an ...
1
vote
0answers
72 views

“Barrier functions” in function spaces [closed]

In general the idea of a "barrier function" (as in the context of "interior point methods") can possibly be thought of as defining a function corresponding to an open subset of $\mathbb{R}^n$ such ...
0
votes
1answer
44 views

Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem $$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...
0
votes
0answers
24 views

Should penalty and Lyapunov drift be normalised in drift-plus-penalty optimisation?

I want to use drift-plus-penalty method to optimize control decisions in the system that I am considering in my research. In particular, I want to minimize penalty function (which in my case is ...
1
vote
1answer
114 views

Feasibility Mixed integer Linear programming with quadratic constraints?

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
0
votes
2answers
80 views

On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
3
votes
1answer
100 views

Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
0
votes
0answers
84 views

Is this Graph Iteration Already Known?

When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
0
votes
0answers
63 views

Faster Mixed Integer Linear Programming Searchless Feasibility

We know Lenstra's Mixed Integer LP with Kannan's modificiation solves feasibility Mixed Integer LP in $n$ integer variables, $r$ real variables and $m$ constraints by solving the search version in $n^{...
0
votes
0answers
39 views

linear inequalities and reference request

I have proved and am using the following simple lemma in my current research problem: Let $\{a_1,...,a_m\}$ and $\{b_1,b_2,...,b_n\}$ be set of positive numbers such that $\sum_{i=1}^m a_i < \sum_{...
0
votes
0answers
16 views

Algorithms for Simple Paths with Minimum Cost-to-Time Ratio

This question is related to Graph-theoretic Algorithm for Path with Minimum Average Edge Length, but in this one is about the LP formulation. Preconditional "facts": Linear fractional ...
1
vote
1answer
128 views

Optimization of a continuous function

This is more like an optimization problem but any solution is appreciated. I have a data set with input specifying power(demand) to be generated for a particular time period(TP). Input: Time --- ...
1
vote
0answers
47 views

On number of solutions by simplex and number of solutions in total in a linear optimization problem?

This is more of a clarification query. Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem $$\max c'x$$ $$Ax\leq b$$ where $A\in\...
1
vote
0answers
53 views

Possible ordering of coordinates in a linear subspace [closed]

This question was asked on Mathematics Stack Exchange with no answers. Let $X$ be a linear subspace of $\mathbb{R}^n$. For how many permutations $p$ on $1,...,n$ does there exists $x$ in $X$ with $...
2
votes
1answer
43 views

Linear program with one quadratic condition convex in domain of interest polynomial time solvable?

$c\leq xy$ is not a convex condition. However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$. Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...
1
vote
0answers
42 views

LP Constraints for Bridgeless Cactus Graphs

When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck. What I do not know how to capture, is the variable number and sizes of the ...
0
votes
0answers
37 views

Finding a point in the relative interior of the convex hull of a set of integer-valued vectors

Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
1
vote
0answers
44 views

On the defect of a flow network

This problem in graph theory was actually motivated by some problems in Theory of Fractals. To formulate the problem I need to recall some definitions related to flow network. A flow network is a ...
1
vote
0answers
67 views

Infinite system of equations with finitely many constraints

During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
0
votes
0answers
44 views

On integer programming augmented with Barvinok's counting version?

Suppose we have an Integer Linear program with $m$ number of inequalities and $n+2$ integer variables ($a_1,\dots,a_n,x,y$). We introduce two extra variables $t$ and $u$ and inequalities $$1\leq t\...
0
votes
0answers
20 views

Can the coordinate system in a three dimensional space be corrected for the maximum function when using the simplex algorithm?

Tldr: Is it possible to somehow correct a coordinate system by the maximization function when using the simplex algorithm so it would be possible to just always follow the steepest slope from point to ...
5
votes
0answers
77 views

What is the LP gap of vertex cover in planar graphs?

What is the LP gap of vertex cover in planar graphs? The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $ $ c_e \geq 0 $ are ...
24
votes
3answers
673 views

Is the Ford-Fulkerson algorithm a tropical rational function?

The Ford-Fulkerson algorithm Let me recall the standard scenario of flow optimization (for integer flows at least): Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
1
vote
0answers
105 views

How to solve a large linear programming problem? [closed]

I have the linear programming problem in $\mathbf x \in\mathbb R^n$ $$\begin{array}{ll} \text{minimize} & \mathbf c^T\mathbf x\\ \text{subject to} & \mathbf A\mathbf x \leq \mathbf b\end{...
5
votes
0answers
141 views

Homogeneous linear and quadratic inequalities

I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that $$...
1
vote
1answer
106 views

a linear programming problem

Recently I have a conjecture on decomposing a linear program into smaller ones. I have tested it in Mathmatica by a lot of examples. However, I cannot prove it. I will appreciate if someone can give ...
5
votes
1answer
97 views

Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
1
vote
0answers
40 views

In convex optimization we know that the optimum solution is on which hyper plane

We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
-1
votes
1answer
95 views

Does a half plane contain intersection of some other half planes? [closed]

I'm doing research in Optimization and I have found this obstacle in the way. If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
0
votes
1answer
55 views

Is an exact violated inequality constraint met as equal constraint in optimal solution?

We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
2
votes
0answers
107 views

Derivative with multiple summation operators

I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following: \linebreak $V$ is the set of nodes, $v_i\in V$; $O$...
6
votes
1answer
144 views

Definition of packing property

Definition 1: A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property. where, vertex cover of $C$ is a set of vertices that have non-empty ...
4
votes
0answers
88 views

$\ell^1$-norm minimization duality

I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\...
1
vote
0answers
171 views

Prove that the following set of triples forms a convex polytope

Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define: \begin{equation} x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;. \end{equation} I would like ...
2
votes
0answers
32 views

Partitioning $n$-space based on linear combinations

I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
4
votes
0answers
124 views

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
1
vote
1answer
100 views

Complexity Measures for Mathematical Programming

Question: Are there any complexity measures in use, that allow one to compare mathematical programming formulations of optimization problems on basis of the number of variables that must be ...
3
votes
1answer
267 views

Under what conditions does an Integer Programming problem run in polynomial time?

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
3
votes
1answer
52 views

LP Constraints for Connected Subgraphs of Fixed Size

Question: how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$? ...
1
vote
0answers
26 views

Computation of sub-gradient for a concave envelope

Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
1
vote
0answers
40 views

Maximizing sum of homogeneous functions of order one over a polytope

Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a homogeneous function of order one for ...
2
votes
0answers
61 views

Are there scenarios under which feasibility bilinear programming is easy?

Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
1
vote
1answer
225 views

What does the basis of the null space of the constraint matrix of a flow problem look like?

Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form: $$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$ ...
1
vote
0answers
162 views

How to find a positive solution to an under-determined linear system (if such a solution exists)?

Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently? Suppose we have an under-determined system: $$Ax = b$$ ...
1
vote
0answers
18 views

Calculating Cost-Optimal 1-Factors in Digraphs

I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...