# 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

0
votes

0
answers

23
views

### Any idea of solving an optimization problem with cubic constraints?

I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...

-3
votes

0
answers

18
views

### Random Value Boundary Matrix [closed]

I stumbled upon this problem during work where I had location (x,y) and depth (z) data for the perimeter of a given area. I created a sample matrix (10x10) that contains only the boundary elements of ...

1
vote

2
answers

101
views

### How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...

2
votes

0
answers

56
views

### Techniques for solving linear inequalities

For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...

0
votes

0
answers

39
views

### Ride sharing problem in GAMS

In this problem, we have a weighted and directed graph, where each node represents a certain place to determine the origin of the driver and the origin and destination of the passengers. In the real ...

0
votes

1
answer

62
views

### Constrained linear optimization problem on $C^1$

I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...

1
vote

0
answers

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

0
votes

0
answers

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

0
votes

0
answers

138
views

### Bound on solutions of $Ax \ge b$

Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...

0
votes

0
answers

73
views

### 1-degree SOS proof refutes Linear Programming

I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...

1
vote

1
answer

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

0
answers

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

0
answers

122
views

### Closed-form solution of a particular linear program

(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...

1
vote

1
answer

68
views

### Best projection on non-convex discrete set with two constraints

I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...

2
votes

1
answer

52
views

### Counting the number of pair of d-uplets with upper bounded distance

Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...

0
votes

1
answer

97
views

### Is there a redundant constraint in linear programming? [closed]

From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...

0
votes

0
answers

138
views

### Finding the eigenvectors of a submatrix

Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...

1
vote

0
answers

32
views

### Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?

EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...

0
votes

1
answer

32
views

### Combining Dantzig-Wolfe and Benders decomposition

I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....

0
votes

0
answers

24
views

### Sensitive analysis of bilevel programs

Given $n+1$ non-negative vectors $r,p_1,\ldots,p_n\in R_{\geq 0}^m$ such that $\|p_i\|_1 =1$ for every $i$ and a series of coefficients $c_1,\ldots,c_n\in R$, consider the following bilevel program:
$$...

0
votes

1
answer

29
views

### Benefit of adding a trivial constraint to ILPs

let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...

0
votes

0
answers

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

0
votes

1
answer

60
views

### How quickly can this IQP or its MILP relaxation be solved

Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...

0
votes

0
answers

30
views

### Matrix optimization to find ideal embedding

Basically, I am trying to find the embeddings so I can approximate $K \approx M(\vec{\phi})$. The embeddings are for each one of my samples $\vec{\phi}(x_i) \in \mathbb{R}^D$ so I thought it should ...

0
votes

1
answer

95
views

### Method for (binary) optimization under constraints

I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...

0
votes

0
answers

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

1
vote

0
answers

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

0
votes

0
answers

21
views

### Feasibility of a basis of a linear program and a relaxed subproblem

I tend to assume that given $$\min c^\top x \\\ Mx=q$$
$$
\text{where} \\ q = \begin{pmatrix}b \in \mathbb R^m\\d \in \mathbb R^n\end{pmatrix},\\M \in \mathbb R^{(m+n)×2n},\\M=\begin{pmatrix}A\\Q\end{...

0
votes

1
answer

56
views

### $\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem

Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...

1
vote

1
answer

147
views

### Linear programming with "nice" matrices

Consider the following linear programming problem
\begin{array}{ll}
\text{minimize} & \mathrm 1^{\top} \mathrm x\\
\text{subject to} & v\le \mathrm A \mathrm x \le u\\
& \mathrm x \geq ...

1
vote

1
answer

152
views

### Interpreting mincost flow dual variables

Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...

0
votes

0
answers

27
views

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

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

0
votes

0
answers

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

0
votes

1
answer

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

2
votes

1
answer

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

1
vote

1
answer

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

1
vote

1
answer

225
views

### Finding a special solution in a solution set over F2

given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...

0
votes

1
answer

98
views

### What is the best way to choose initial basis when applying simplex method to an equality form of LP?

Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...

4
votes

2
answers

219
views

### Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...

0
votes

1
answer

140
views

### Correct way to conduct equilibrium scaling of linear/integer/MIP program

I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...

1
vote

0
answers

35
views

### Linear programming robustness to input perturbations

I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...

2
votes

1
answer

348
views

### How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]

I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?

0
votes

0
answers

72
views

### Explicit equation for border of the Minkowski sum of sets

Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...

1
vote

0
answers

94
views

### Solution of a simple optimization problem

Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...

0
votes

0
answers

89
views

### The best unitary matrices that approximate a matrix product

Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...

1
vote

0
answers

27
views

### How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...

1
vote

0
answers

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

0
votes

0
answers

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

0
votes

0
answers

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

0
votes

0
answers

78
views

### Why is Gaussian distribution always chosen for smoothed analysis?

I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...