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
-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}...
Hepdrey's user avatar
  • 92
-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} &...
Hepdrey's user avatar
  • 92
-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 ...
Luca T. Castrillón's user avatar
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 ...
graphtheory123's user avatar
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 ...
Prakirt Raj's user avatar
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 ...
eternity's user avatar
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,\\ &...
Manfred Weis's user avatar
  • 12.6k
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Juan Carlos's user avatar
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 ...
LyLa's user avatar
  • 3
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}$ (...
Diego Fonseca's user avatar
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 ...
LyLa's user avatar
  • 3
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. ...
Pipnap's user avatar
  • 101
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Connor's user avatar
  • 251
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, ...
Makogan's user avatar
  • 123
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}^...
lzzz's user avatar
  • 1
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} [ ...
Boby's user avatar
  • 631
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 ...
user2512443's user avatar
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 ...
mlogm's user avatar
  • 11
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 ...
Brauer Suzuki's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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} {\...
Erik's user avatar
  • 21
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$. ...
user3750444's user avatar
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 ...
Dmitry's user avatar
  • 221
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 \...
Hyperbolic PDE friend's user avatar
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 ...
ZZZZZZ's user avatar
  • 11
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\|_{...
user1868607's user avatar
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(...
Tom Keaton's user avatar
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). ...
Ryszard Eggink's user avatar
1 vote
0 answers
82 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)$ ...
shahulhameed's user avatar
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:}$$ $...
Fabius Wiesner's user avatar
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;\...
Goga's user avatar
  • 47
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$ ...
Ludwich's user avatar
  • 55
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, ...
Bipolo's user avatar
  • 3
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}=...
ABB's user avatar
  • 3,898
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 ...
Vojtěch Kovařík's user avatar
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....
tlu's user avatar
  • 3
0 votes
1 answer
33 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}}^*}\...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
88 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 ...
Robin Lee's user avatar
0 votes
1 answer
77 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\{...
alosc's user avatar
  • 71
0 votes
1 answer
230 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} & \...
kris's user avatar
  • 3
1 vote
0 answers
45 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$, ...
C_A_Pepe's user avatar
0 votes
1 answer
93 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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
user12345678's user avatar
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} &...
Oleksandr  Kulkov's user avatar
0 votes
1 answer
62 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 =...
Giuseppe Teodoro's user avatar
2 votes
1 answer
222 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 ...
LeechLattice's user avatar
  • 9,411
2 votes
1 answer
330 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 ...
Jochen Wengenroth's user avatar
1 vote
1 answer
279 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{...
borekking's user avatar

1
2 3 4 5
10