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.

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