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.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
123 views

Is this regression problem solvable? [duplicate]

I have a random vector $\pmb{x}=(X_1,...,X_p)^T\in \mathbb{R}^p$, a symmetric matrix $$\Theta = \left(\begin{matrix}0 & \theta_{12} & \theta_{13} & \cdots & \theta_{1p}\\ \theta_{12} &...
-1 votes
0 answers
64 views

Symmetric linear least-squares solution with known diagonal elements [closed]

Given matrices $\pmb{A}\in\mathbb{R}^{p\times n}$ and $\pmb{B}\in\mathbb{R}^{p\times n}$ with $p>n$, I need to solve the following linear system in symmetric matrix $\pmb{X}\in\mathbb{R}^{p\times p}...
-1 votes
0 answers
38 views

Approximating least squares solution with linear programming

Consider the least-squares problem with linear constraints $$(P_2)\quad\text{Min }||Ax-b||^2_2\\ Mx\leq d\\ x\in\mathbb{R}^n$$ where WLOG $b\geq 0$. Probably it's a good approximation of $(P_2)$ to ...
1 vote
1 answer
103 views

$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
0 votes
0 answers
37 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 ...
0 votes
0 answers
25 views

Application of greedy approach for optimization

I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$ where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
8 votes
2 answers
924 views

Minesweeper as a linear algebra problem

I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
1 vote
1 answer
278 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{...
2 votes
1 answer
200 views

Is matrix B obtained from matrix A?

Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
9 votes
2 answers
767 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 \...
3 votes
1 answer
341 views

Lot sizing problem: how to add these cuts efficiently

Consider the set of constraints of the uncapacitated lot sizing problem: $$ \{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
0 votes
1 answer
233 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 ...
0 votes
0 answers
33 views

ILPs with square constraint matrix

Given the Integer Linear Programming ($\text{ILP}$) problem \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to}& \mathbf{A}^T x \ge b \\ \text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
2 votes
0 answers
112 views

Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$

Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
1 vote
0 answers
68 views

Fundamental regions in convex programming

In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
0 votes
0 answers
24 views

Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's ...
0 votes
0 answers
146 views

Solve NP-hard type problems with linear programming

I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force. I ask this ...
0 votes
0 answers
48 views

Alternatives to McCormick Envelope

I have an optimization problem for which I have the optimal solution obtained by the ILP. However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
1 vote
1 answer
492 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
2 answers
273 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} {\...
0 votes
1 answer
110 views

How to integrate an indicator function/constraint into the cost function of a linear program?

I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$. In $F_2$, I want it to be included only when its expression ...
0 votes
0 answers
135 views

Inf-convolution of norm 1 and norm 2 square

The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is $$ h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) . $$ We can prove that if $f,g$ are convex functions, then $h$ is convex. ...
0 votes
1 answer
26 views

Calculating vertex potentials from optimal matchings

Question: can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program? If yes, what are known algorithms and their bounds on complexity. As ...
0 votes
0 answers
71 views

An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$, $$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$ where $uv$ is an ...
1 vote
1 answer
175 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 ...
2 votes
1 answer
111 views

Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
0 votes
0 answers
54 views

Relationship of optimal solutions between the total function and the sub function

This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
0 votes
0 answers
80 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} [ ...
1 vote
1 answer
63 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 ...
0 votes
0 answers
37 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 ...
1 vote
1 answer
95 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 ...
4 votes
3 answers
921 views

Minimax theorem on a non convex domain

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$: $$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
0 votes
0 answers
20 views

LP formulation of $k$-opt moves

Question: what is known about formulating $k$-opt moves that strive for improving the length of Hamilton cycles by means of exchanging $k$ of the tour edges with $k$ non-tour edges? Specifically: are ...
1 vote
2 answers
116 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
64 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 ...
2 votes
3 answers
2k views

Better tactics for removing redundant constraints than Linear Programming?

After reading: Detection of Redundant Constraints It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form $$ ...
0 votes
1 answer
88 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
26 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
144 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\|_{...
1 vote
1 answer
95 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). ...
0 votes
0 answers
82 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
0 answers
81 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
221 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
114 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
56 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
126 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
226 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
37 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
62 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
1 answer
354 views

Computing discrete optimal transport

I am trying to find a combinatorial approach to solve the following optimization problem. \begin{align} &\max_{x_{ij}} C_{ij} x_{ij}, \\ &\text{such that},\\ &\sum_{j} x_{ij} \leq r_i~\...

1
2 3 4 5
10