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

484 questions
Filter by
Sorted by
Tagged with
74 views

### Software for computing polytopes

As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
163 views

### Efficient counting of integer solutions to linear system

In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
• 151
39 views

### Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
39 views

### Max-flow modeling with unified vehicle and commodity variables

I am working on a network flow problem that involves routing through a time-space network. The network consists of: A single source node and a single demand node. A fleet of vehicles with specified ...
27 views

• 1
82 views

### Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points

Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$ \begin{align} \max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
• 631
1 vote
65 views

### $A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance

Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
• 111
1 vote
101 views

### Optimization on non-convex set

Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem $$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$ where a minimum is ...
• 11
38 views

### Basis of monoid of integral vectors

Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...
360 views

1 vote
32 views

### Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?

Suppose that $P$ is a polyhedron represented by $$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$ and $P$ contains interior points. Moreover, the ...
• 33
144 views

1 vote
109 views

### Adding linear constraint to the domain

I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm. I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
1 vote
89 views

### On optimizing a multivariate quadratic function subject to certain conditions

The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
1 vote