Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
5,123
questions
0
votes
0
answers
17
views
Mapping this problem from solving the Minimum Cost Flow to solving the Max Flow problem
I'm trying to implement the algorithm described in FD21.
In particular, this is the optimization problem (problem 2 in the paper).
Find the liability matrix $M$ of the obligation network $M$ such that ...
0
votes
1
answer
17
views
Mutually exclusive non-zero variables in Linear Programming, without using binary variables or objective function
First, apologies for the probably terrible title. I could not think of a better one.
I am creating an LP model in which all variables are non-negative. I have the following constraints:
$$a - b = c - ...
- 103
0
votes
0
answers
24
views
Characterizing the Result of Lift and Project Method for Integer Programming
I have the following integer linear programming problem:
Let $P=\{x\in \mathbb{R}^n\colon Ax\geq b\}\subseteq [0,1]^n$ be a polytope. For a fixed index $j\in [n]$, consider the polyhedron $P^j$ ...
- 2,504
2
votes
1
answer
24
views
Path-following methods being a 1-phase method
I read in Vanderbei's "Linear Programming" that "The path-following method is a one-phase method. This
means that the method can begin from a point that is neither primal nor dual ...
1
vote
0
answers
64
views
Converting $x^3$ Optimization to an Equivalent LP Problem
Suppose we want to find the minimum of a a strictly increasing function $f: [-a, a] \to \mathbb{R} $, for some $a > 0$, which is also concave in $[-a, 0]$ and convex in $[0, a]$ (exactly like the $...
- 11
0
votes
1
answer
42
views
Does LP have optimal solution provided that the coefficients and variables are guaranteed to be nonnegative?
Suppose that $A$ is an $m$ by $n$ real matrix, $c$ and $x$ are $n$-dimensional real vector, and $b$ is an $m$-dimensional real vector. Let '$\le$' be an elementwise partial order between two vectors. ...
- 174
2
votes
0
answers
33
views
For each vertex $v$ of a polytope $P$, is vertex $v$ the unique optimal solution to some linear program over $P$?
Is it true that for every vertex $v$ of a polytope $P$, three exists some linear programming specification with $P$ as the feasible region for which vertex $v$ is the unique optimal solution?
If this ...
- 21
1
vote
1
answer
63
views
Chvatal-Gomory integer rounding method to find facets of $\operatorname{conv}(S)$
The question:
"given a set $S = \{x \in \mathbb{Z}^2 : 4x_1 + x_2 ≤ 28, x_1 + 4x_2 ≤ 27, x_1 − x_2 ≤ 1, x ≥ 0 \}$.
we are tasked with deriving each facet of $\operatorname{conv}(S)$ as a Chvatal-...
- 13
0
votes
0
answers
26
views
Quadratic Programming and Betweenness Problem
Given Betweenness problem of $n$ variables $x_1,...,x_n$ and $m$ triplets $(x_i,x_j,x_k)$, I build a Quadratic Programming for the triplets such that for every triplet $(x_i,x_j,x_k)$ I add $(2x_j-x_i-...
user411780
2
votes
1
answer
68
views
0-1 Linear programming and non-optimal multidimensional knapsack
I would like to create a set of constraints forcing a set of knapsacks to be filled. The knapsacks should be filled, so that no further element of a set of elements fits into it. It is not a classical ...
- 255
3
votes
1
answer
90
views
Existence of solutions in linear programming
If a linear programming problem "maximize $c^{\top} x$ with $Ax \leq b$, $x \geq 0$" is feasible (there is an $x$ satisfying the constraints) and bounded from above (there is a number $M$ ...
- 512
0
votes
0
answers
30
views
Incremental algorithm for 2D Linear Programming question for feasible points
I have the following problem that I want to solve using linear programming:
$\max\{-3x+12y\}$ (objective function) and 4 contraints: $-x+2y\leq-1$, $2x-3y \leq 6$, $x-3y \leq 0$, $x+y\leq12$
I start ...
2
votes
2
answers
118
views
Is there a Python library that would solve a quadratic optimization problem?
I am trying to optimize a quadratic formula, where I have to simultaneously find a maximum wrt. $x$ and a minimum wrt. $y$.
More precisely, let
$F(x, y) = x M y + x 1^n$, where:
$x$ - is an n-...
- 410
0
votes
0
answers
26
views
Existence of a basis of lattice with successive minima norms
Is there an easy way to show that given a lattice $\Lambda \subset \mathbb{R}^n$ of full rank, exists a basis where each vector has norm $\lambda_i$ i.e the i-th successive minima ($\lambda_i(\Lambda)=...
- 5,164
0
votes
1
answer
48
views
Show boundedness of set if optimization problem has a global solution
Show that a non-empty closed set $\Omega \subset \mathbb{R}^n$ is compact iff for every $c \in \mathbb{R}^n$ the problem $\min c^Tx,x\in \Omega$ has a global solution.
For "$\Rightarrow$" I ...
