# Questions tagged [linear-programming]

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.

**10**

votes

**3**answers

572 views

### Famous theorems that are special cases of linear programming (or convex) duality

The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...

**0**

votes

**0**answers

21 views

### Maximizing the sum of piecewise linear functions using approximate, differentiable functions

Given an arbitrary (sorted) set of numbers $\{c_1,\dots,c_n\}$, define for each number the piecewise continuous linear function
$$
f_i(x) =\begin{cases}
x & 0\leq x\leq c_i \\
0 & ...

**4**

votes

**1**answer

65 views

### Sampling uniformly from the vertices of a polytope

I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...

**6**

votes

**1**answer

140 views

### How did they come up with the MRRW bound?

Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is
Suppose $C \...

**0**

votes

**0**answers

20 views

### Fairly allocating heterogenous items

I'm trying to find literature on what I'm sure is a well-understood mathematical problem, but am struggling for terminology.
Let's say I have a number of items each of which is either shiny or matte, ...

**0**

votes

**0**answers

46 views

### Polynomial time way of testing optimality of given vertex for linear programming

Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy?
I can find the optimal vertex in worst-case polynomial ...

**0**

votes

**1**answer

74 views

### How good is the LP relaxation?

Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...

**0**

votes

**0**answers

9 views

### How to Create Point-Optimal Objective Functions

Here is a problem that has originated from some IP research i'm working on.
You are given a polyhedron $P$ in standard matrix inequality form of $Ax \le b$, $x \in \mathbb{R}^n$ as well as a point $...

**0**

votes

**2**answers

85 views

### Does Max Flow produce uniform results? [closed]

I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...

**1**

vote

**3**answers

105 views

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

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

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

**0**

votes

**1**answer

114 views

### How to solve this optimization problem efficiently? [closed]

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

**1**

vote

**1**answer

69 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

69 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

221 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

27 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

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

**5**

votes

**1**answer

134 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

75 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

62 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

34 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

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

**-1**

votes

**2**answers

84 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

111 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

87 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

74 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

24 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

133 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

48 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

51 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

67 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

45 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

68 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

81 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

710 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

109 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

142 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

112 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

116 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

98 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

59 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

135 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

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