Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
5,129
questions
0
votes
0
answers
32
views
Prove the summability.
I'm reading a paper on distributed optimization and need to use the supermartingale theorem using summability. How can I prove that:
$$\sum_{k=0}^{\infty}\alpha(k)\sum_{s=0}^{k-1}\lambda_1^{k-1-s}\...
-2
votes
0
answers
29
views
Algebraic form of the Simplex tableau fill in the blanks question [closed]
This image is from a linear programming exam question f
The teacher refuses to give a solution but I cannot find it myself, I know that x5 will be basic and the ? in the RHS will be 0, but what will ...
- 1
0
votes
1
answer
41
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
29
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
62
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
-4
votes
0
answers
44
views
Formulate the goal programming model that can be used to minimize the penalty incurred by the company [closed]
A company produces two products. Relevant information for each product is shown in
Table below. The company has a goal of \$48 in profits and incurs a \$1 penalty for
each dollar it falls short of ...
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-...
- 712
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
2
votes
1
answer
86
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$ ...
- 502
0
votes
0
answers
28
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
117
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-...
- 400
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
45
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 ...
1
vote
0
answers
41
views
What is the maximum number of (non-overlapping) small squares that fit inside a larger square? And similar question for cubes.
I am having a hard time answering the following questions, despite them seeming elementary at first glance.
Is it true that the maximum number of (non-overlapping) squares with side lengths $x$ cm ...
- 20.6k
0
votes
0
answers
22
views
Multiple optimal solutions in Simplex method when solving Linear Programming
What is the Simplex tableau would be if there are multiple optimal solutions in solving Linear Programming.
I think there must be a test number $r_j$ for a nonbasic variable $x_j$ equals 0. And at ...
- 61