Skip to main content

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.

20 questions from the last 365 days
Filter by
Sorted by
Tagged with
3 votes
1 answer
150 views

How to maximize the variance of a subset of integers?

$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
Hasan Zaeem's user avatar
1 vote
0 answers
29 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
Sowbarnika R's user avatar
-1 votes
0 answers
41 views

Is it possible to backtrack an optimization solver? [closed]

I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
Bamboozle's user avatar
0 votes
0 answers
21 views

Easy instance of set cover

I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
Tom Solberg's user avatar
  • 4,049
7 votes
2 answers
242 views

Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$

Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds: $$ \langle x_k, \theta_k \rangle &...
Alireza Bakhtiari's user avatar
2 votes
4 answers
212 views

Efficient algorithm for graph problem

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
Martin Clever's user avatar
1 vote
1 answer
106 views

Iterated optimal transport

Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
tex.support's user avatar
0 votes
0 answers
48 views

A question on a quantitative form of Farkas' lemma

Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
Keivan Karai's user avatar
  • 6,214
1 vote
0 answers
99 views

Minimum of the maximum element frequency given the family size and the universe size

[Crossposted at math.stackexchange]. Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$. I have written and solved ...
Fabius Wiesner's user avatar
0 votes
0 answers
115 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 ...
AlexiosF's user avatar
5 votes
1 answer
176 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 ...
user326210's user avatar
4 votes
0 answers
46 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 ...
mashedcarrots's user avatar
0 votes
0 answers
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 ...
graphtheory123's user avatar
0 votes
0 answers
30 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
213 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
36 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
  • 13.2k
0 votes
0 answers
26 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
  • 13.2k
0 votes
0 answers
171 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
64 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
119 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