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

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
3answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
3answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
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
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
1answer
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
0answers
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
0answers
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
1answer
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
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
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
0answers
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
0answers
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
0answers
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
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
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
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
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
1answer
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
0answers
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
1answer
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 ...