As of May 31, 2023, we have updated our Code of Conduct.

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

473 questions
Filter by
Sorted by
Tagged with
23 views

• 115
1 vote
21 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 ...
• 11
13 views

### ILP formulations for tour-improvements

Question: what is known about the problem of formulating tour-improvement as an integer linear problem (ILP)? To be specific: what are necessary and/or sufficient constraints, besides the degree-...
• 12k
138 views

1 vote
75 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
63 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
122 views

• 12k
69 views

### Boolean operation on n dimensional polyhedron

A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$. Given a set of polyhedra in $R^n$, $P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
60 views

• 3
27 views

### Partially relaxing integer programs while preserving unique integral solution

Consider the program $$\exists x\in\mathbb Z$$ $$\exists y\in\mathbb Z^d$$ $$A[x,y]'\leq b$$ and assume exactly one $(x_0,y_0)\in\mathbb Z^{d+1}$ satisfies the program. Under what conditions on $A,b$ ...
• 13.4k
1 vote
31 views

### How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?

I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
• 11
21 views

27 views

### Efficient way to Non linear constraint programming with polynomials

I have a non-linear programming constraint problem as below: \begin{split} minimise_{x \in \mathbb{R}^n} &f(x) \\ subject\ to\ &c(x)>= 0\\ &l_i<= x_i <= u_i,\ ...
92 views

### Prove that we can construct a joint probability distribution from its marginals: a linear programme

I do research in statistics and I would like to understand if I can construct a joint probability mass function from its marginals, under some constraints. This problem can be formalised as a linear ...
• 57
57 views

### Round Robin volleyball Tournament [closed]

Consider a set of N teams (N even number) that must make a Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level of interest si,j ∈ {1;2;3} of the match between them (1 =...
205 views

### Solving linear programming without solving linear programming

Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them. It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
• 9,108
1 vote
284 views

### Who called Farkas' fundamental theorem a lemma?

Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
• 14.4k
1 vote
225 views

• 12k
1 vote
95 views

### Drawing a 3D object in a 3D environment, and converting to math [closed]

So I have been granted a free time and I want to work on a project but first I had to research. As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...
81 views

### How to find a set given its support function

Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function \$\delta^*(v|\...
• 53
34 views

### Subtour-gluing constraints for ILP formulation of TSPs

If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
• 12k