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.

**-1**

votes

**0**answers

25 views

### Literature request: Function that depends on a linear optimization problem

my question is about functions of the following form:
$$ f(t) = \max_{\mathbf{x}}~ \mathbf{c^T x} ~ {\rm s.t. \mathbf{Ax} +t \cdot \mathbf{a} \leq \mathbf{b}}, $$
where $\mathbf{x},\mathbf{b}, $ ...

**0**

votes

**0**answers

18 views

### A question related to parametric linear programming

Consider the following parametric linear problem:
\begin{align}
\min z(t)=c^T x\\
Ax=b(t)\\
0\leq x\leq u.
\end{align}
We know $z(t)$ is a piecewise linear function. Let $x(t_1)$ and $x(t_2)$ be the ...

**1**

vote

**1**answer

108 views

### How to solve this optimization problem efficiently?

Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...

**0**

votes

**0**answers

28 views

### how to get this deterministic equivalent formulation of its original probabilistic counterpart by knapsack constraint?

I'm reading this article with title "a probabilistic model applied to emergency service vehicle location". https://www.sciencedirect.com/science/article/pii/S0377221708002336
This is a very good ...

**0**

votes

**0**answers

34 views

### a game-theoretical / optimization problem

Does anyone know how to solve (or a good reference) for the following problem?
Let n and m be two positive integers. Let z \mapsto G^{i,j}(z) be a real polynomial, for each i=1,...,n and j=1,...,m. ...

**1**

vote

**1**answer

68 views

### LASSO problem but with a maximization instead of minimization

I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...

**-1**

votes

**1**answer

67 views

### sparse data fitting problem [closed]

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

**6**

votes

**1**answer

210 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

**0**answers

25 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

**0**answers

29 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

**0**answers

63 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

**1**answer

109 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

**0**answers

74 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

**1**answer

52 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

**0**answers

29 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

**1**answer

122 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

**2**answers

81 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

**1**answer

106 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

**0**answers

86 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

**0**answers

65 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

**0**answers

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

**0**answers

18 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

**1**answer

132 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

**0**answers

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

**0**answers

54 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

**1**answer

47 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

**0**answers

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

**0**answers

47 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

**0**answers

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

**0**answers

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

**0**answers

46 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

**0**answers

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

**0**answers

78 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

**3**answers

692 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

**0**answers

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

**0**answers

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

**1**answer

108 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

**1**answer

104 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

**0**answers

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

**1**answer

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

**1**answer

57 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

**0**answers

128 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

**1**answer

149 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

**0**answers

89 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

**0**answers

174 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

**0**answers

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

**0**answers

125 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

**1**answer

101 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

**1**answer

279 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

**1**answer

56 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$?
...