Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
1
vote
1answer
12 views
Formulating a LP minimization problem
Attempt
Let $x_i$ be the number of workers to be hired that starts its shift on day $i$. So we want to minimize the function $f( {\bf } ) = \sum_{i=1}^7 x_i$. The constraints:
$$ x_1 \leq 17 $$
$$ ...
0
votes
0answers
18 views
Kuhn Tucker conditions for a linear programming problem
What are the KKT conditions for the following linear programming problem:
Or in other words, how can we go from that problem to this one:
min v x subject to $Dx\ge u$
0
votes
0answers
9 views
Variable as an index in linear programming
Is it possible to use a variable as an index in linear programming ?
For example
$\sum_{t=0}^{y}x_{t}= a$
where y is a variable (and also $x_{t}$)
1
vote
0answers
23 views
Properties of max norm as a constraint
If I have the following linear optimization problem (convex):
$$\min Tr(D^TX) \ \ \ \ \ $$
$$s.t. \sum_{i=1}^{N}x_{ij}= 1 \ \ \ \forall j, \ \ \ \ \ \ x_{i,j} \geq 0 \ \ \ \forall i,j$$
$$$$
$Tr(.)$ ...
0
votes
1answer
14 views
Convex polyhedron: Show $B$ is an extremal point and $A$ is not
Given is the convex polyhedron $P:= \left\{\begin{pmatrix} x\\ y
\end{pmatrix} \in \mathbb{R}^2 \mid 5x-2y \leq 7, x \geq 0, y \geq
0\right\}$. Show that $A = \begin{pmatrix} 3\\ 4 \end{pmatrix}$ is
...
0
votes
0answers
47 views
Maximizing Profit - Linear Programming
I'm trying to formulate a linear program for this problem:
There is a blacksmith who can produce $n$ different alloys, where alloy $i$ sells for $p_i$ dollars per unit. One unit of alloy $i$ takes $...
1
vote
1answer
27 views
Create a model from the given text (linear programming/optimization)
I'm practicing for a linear programming test and here is a task I like to see if I did it correct and if not maybe how to do it correctly? Need to create a mathematical model whose requirements are ...
1
vote
2answers
62 views
Linear Programming - Maximization Question
I'm working on this problem right now:
You are a jeweler who sells necklaces and rings. Each necklace takes 4 ounces of gold and 2 diamonds to produce, each ring takes 1 ounce of gold and 3 ...
0
votes
0answers
16 views
Constructing an extreme direction from a simplex tableau indicating unboundedness
Context: In a question, we are asked to show that a problem does not have a finite optimal solution, then told to construct an extreme direction of the feasible region using the final tableau.
The ...
0
votes
1answer
37 views
How to formulate $\min \|X-z^T\mathbf{1}^T\|$ as a least squres problem?
Suppose $X\in \mathbb{R}^{m\times n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables).
Suppose I have $$\min_{x,z} \|X-z\mathbf{1}^T\|^...
1
vote
1answer
30 views
Attempting to solve a linear program using Maxima, but problem unbounded.
As the title says, I'm attempting to use Maxima's minimize_lp(objective,conditions,nonegative=true) to solve a linear program, where the function $z(x_1,x_2,x_3) = ...
1
vote
1answer
24 views
Question about alternative optimal extreme points?
Could someone please check if what I've done is correct? And how could I answer b. ?
Thank you.
Consider the following
$$\max 2x+3y\\ s.t.\ \ x+y\le2\\ 4x+6y\le9\\ x,y\ge0$$
a. Sketch the ...
0
votes
0answers
11 views
Can I add two types of variables by column generation?
Suppose I have a LP as the one written as follows:
min c'x + h'y
s.t:
Af <= a
Bf + Dy <= b
Gf + Mx <= d
f in F
y in Y
x in X
If the set X is huge, I can generate the x variables ...
1
vote
0answers
30 views
A linear program with unbounded optimal solution
Consider the following
$$\max 3x_1+x_2\\ s.t. -x_1+2x_2\le0\\ x_2\le4$$
a) Sketch the feasible region
b)Verify that the problem has an unbounded optimal solution value
Attempt:
a) (Here the ...
0
votes
1answer
20 views
How to perform a linear fit of a path in the plane?
I have an ordered set of $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ and I would like to choose an ordered subset of these points, say $(x_{k_1},y_{k_1}),\dots,(x_{k_s},y_{k_s})$, with $(x_{k_1},y_{k_1})=(...
0
votes
1answer
19 views
Convex hull of union of nondisjoint polyhedra
Is there a theorem which proves that the convex hull of the union of nondisjoint polyhedra is also polyhedral?
1
vote
0answers
30 views
How to model a simple market equilibrium with linear programming?
I want to model the following problem. The problem is well-known in economics. demand-supply curve equilibrium.
Is there any straight forward technique to solve the equilibrium point obtained by an ...
1
vote
1answer
29 views
Finding the dual of a Linear program
suppose we have
$$ min z = 6 x_1 + 20 x+3 $$
such that
$$ x_2 + 4 x_3 \leq 10 $$
$$ - x_2 +2 x_3 \leq 11 $$
$$ x_i \geq 0 $$
Find the dual.
ATTEMPT:
I wrote
$$ max = 10 y_1 + 11 y_2 $$
st
...
1
vote
0answers
12 views
Degeneracy and Uniqueness in General LP
This is about problem 4.12 from Bertsimas & Tsitsiklis's Introduction to Linear Optimization à la page 190. The problem is repeated below (bold is from errata).
Consider a general linear ...
4
votes
2answers
76 views
How to prove that 1/3 is the optimal solution for the muffin problem with 5 students and 7 muffins?
The Muffin Problem
Definition
Let there be $m$ muffins and $s$ students. The problem is to divide the muffins into pieces where every student gets exactly $\frac m s$ muffin, such that the size of ...
1
vote
0answers
17 views
How to find an optimal solution of the dual from the primal tableau?
The tableau above is an optimal tableau of a LP problem. If I want to find the optimal solution of dual, I know, I can rewrite this in terms of the original problem and remove the slack variables $x_4,...
0
votes
0answers
26 views
About the proof of a theorem about Linear Programming in C. L . Liu “Introduction to Combinatorial Mathematics”
I am reading C. L . Liu "Introduction to Combinatorial Mathematics".
I think his proof of the following theorem is not correct.
Am I right?
p.312 Theorem 12-1
If a linear programming problem ...
1
vote
0answers
22 views
Solution to a primal LP relation to the dual
Suppose we have the following LP
\begin{align*}
\min z = x_1 + 2x_2 \\
x_1 \geq 1 \\
x_1+x_2 \geq 2 \\
x_1,x_2 \geq 0 \\
\end{align*}
We can use simplex or a graphical method to find the optimal ...
0
votes
0answers
25 views
Finding the dual of an LP
For the first part, Once I pivot and make $x_4,x_5$ enter the basis, we can obtain our original problem. Actually, -35 should be -62 so that we get
$$ min z = 6x_1 + 20 x_3 $$
such that
$$ x_2 + 4 ...
0
votes
0answers
15 views
Find all packings of widgets by a set of requirements: is this a linear programming or combinatorial optimization, or bin packing problem??
Can not determine if this is a linear programming problem, or a combinatorial optimization problem, or even a packing problem?
Goal is to allocate widgets from the inventory to fulfill all shipping
...
1
vote
1answer
39 views
Finding the dual of a linear programming problem
Consider the LP
$min f(x_1,...,x_n) = \sum_{i=1}^n i x_i $
such that
\begin{align*} x_1 \geq 1 \\ x_1 + x_2 \geq 2 \\ ... \\ x_1 + ... +
x_n \geq n \end{align*}
Im trying to ...
1
vote
2answers
66 views
MILP: Minimizing $|Ax-b|$ with at most 5 x variables being non-zero
I have a $m \times n$ matrix $A$, where $n$ is very large and $ n>m$ (underdetermined), and $b$ is $m \times 1$ matrix. I want to minimize $|Ax-b|$, but at most $5$ $x_i$ can be non-zero. Other ...
0
votes
0answers
17 views
Slack variables insertion in primal-dual couple
Suppose we have the following primal-dual couple:
(P1) Min $z_1 = c^Tx$
s.t.
$Ax >= b$
$x >= 0$
(P2) Max $z_2 = b^Ty$
s.t.
$A^Ty <= c$
$y >= 0$
If we introduce slack ...
0
votes
0answers
15 views
Nearest signed permutation matrix to a given matrix $A$
Let $A \in \mathbb{R}^{n\times n}$ be a square matrix and let $Q \in O(n)$ be the nearest orthogonal matrix to $A$ under the Frobenius norm, i.e.
$$Q = \text{arg}\min_{M \in O(n)} ||A - M||_{F}^2$$
...
0
votes
0answers
20 views
Linear Programming - Different decision variables
APEX Company produces and sells three products: X, Y and Z. In order to produce them, the company needs to purchase four raw materials A, B, C and D. The prices of these four raw materials are $15/kg, ...
1
vote
1answer
23 views
Efficient way of checking if a set is convex in 3 or more dimensions?
Consider the following set:
$$C:=\Bigg\{\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}: x_3=\lvert x_2\lvert,\:x_1\leq3\Bigg\}$$
Now, I can graph this using a program, like Mathematica, and tell visually ...
0
votes
1answer
21 views
Interpretation of a restriction of a linear programming problem
I'm trying to model the number of new planes an airline must buy. There are 3 types: small, medium and big. Let $x_i$ be the number of new planes of type $i$ that the airline buys (1=small, 2=medium ...
0
votes
0answers
34 views
About Simplex method in Introduction to Algorithms (CLRS)
I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
I think it is obvious that $28$ is the optimal objective value from the objective function $z = 28 - \frac{1}{6} x_3 - \frac{1}{6} x_5 - \...
5
votes
2answers
118 views
Transform an optimisation problem into a linearly-constrained quadratic program?
I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
0
votes
0answers
21 views
Finding relationship between input and output
I am just trying to figure out what key words I should look up to help me with the following problem.
I have a control system to control a PWM motor and a sensor to detect the motors frequency for ...
0
votes
0answers
18 views
How can I linearize a nonlinear constraint in LP model
I have a question about the linearization of nonlinear constraints in LP models.
For example a simple LP like this:
minimize
$$
x_1+x_2+f(x_1,x_2,x_3)
$$
subject to
$$
x_1+ x_2^2\le1 \\...
0
votes
0answers
36 views
LPP vs Convex optimisation
I am studying for my statistics exam and we have Linear Programming,Simplex and graphical method, Duality Programming and Integer Programming. I have a great interest in Convex optimisation and wanted ...
0
votes
0answers
25 views
maximize the maximum value of a linear optimization
Here is my problem, first, $v$ is the optimal value of a LP problem
$$
v = \max_w w^TF\beta
$$
subject to
$$
w \ge 0 \\
Aw = b \\
$$
Then I want to find the coefficient $\beta$ that ...
1
vote
0answers
44 views
Entering and leaving variables in this linear programming problem
Consider the following constraints:
$$
\begin{align}
2x_1+3x_2&\leq6\\
-2x_1+x_2&\leq2\\
x_1-2x_2&\leq0\\
x_1, x_2&\geq0
\end{align}
$$
Suppose that a move is made from extreme point
$...
1
vote
0answers
22 views
Let $S = \{y_1a_1+y_2a_2~|~-1 \leq y_1,y_2 \leq 1\}$ where $a_1 , a_2 \in \mathbb{R}^2$.
Let $S = \{y_1a_1+y_2a_2~|~-1 \leq y_1,y_2 \leq 1\}$ where $a_1 , a_2 \in \mathbb{R}^2$. Show $S$ is a polyhedron. Assume $a_1,a_2$ are linearly independent.
Now I believe this question was asked ...
0
votes
0answers
24 views
Deriving an upper bound for a constrained infinity norm minimization problem
I have the following problem:
$$\min_{x\in X}\|Mx-c\|_{\infty}$$
I am considering a particular case, in which:
$$M=\left[\begin{array}{cc} a & 1-a\\ b & 1-b \end{array}\right], c=\left[\...
0
votes
0answers
15 views
saddle points of lagrangian function on linear programming
i am having some difficulty on showing the following problem,
consider
$$\min c'x$$
$$s.t. \ Ax=b$$
$$x \geq 0$$
and it's dual
$$\max p'b $$
$$s.t. \ p'A \leq c'$$
then the lagrangian function is ...
0
votes
0answers
26 views
Stuck with a Integer Programming problem
I've tried hours and hours to model this problem but i didn't succeed. Can you help me ?
We want to realize n projects in the next T years. For each project, a
profitability index pi is known, ...
0
votes
1answer
22 views
Forcing a series of OR statements in ILP Problem
I am attempting to solve an ILP program in relation to maximizing the return on investments. There are 10 decision variables, $x_1, x_2, ...,x_{10}$, with the following goals:
Max $0.067x_1 + ...+0....
0
votes
1answer
30 views
Variable as subscript in Linear Programming
I have to maximize this function
$max \sum_{i=0}^{n}x_{i}$ , $\bar{x}\in \mathbb{Z}, \bar{x}\geq 0$
is to possible to define this as a constraint ?
$\sum_{t=0}^{T_{i}}M_{i,x_{i+t}}= T_{i}$
(I'm ...
3
votes
1answer
31 views
Transportation problem with the least number of transportations.
I have a non trivial case of transportational problem. Let me get you familiar with it.
We have $n$ suppliers $a_1, ..., a_n$ and $m$ consumers $b_1, ..., b_m$.
The suppliers volume of goods to ...
0
votes
1answer
21 views
Integer and continuous constraints in a linear programming problem
Until now i formulated some Linear Programming problems with integer constraints and some with continuous constraints. Now, i've written a linear programming model that both contains variables with ...
0
votes
0answers
19 views
Example of LP Degeneracy with Unique Basis
In standard form LP, a basic solution is degenerate if there are more than $n-m$ zero variables, as defined in Bertsimas and Tsitsiklis. The authors say, in page 60, that there are examples of ...
0
votes
0answers
11 views
In Simplex Method, can I move from a basic solution $x^{*}$ to the other $y^{*}$ by pivoting zero cost in Tableau?
Suppose that $B_1$ is the bases for $x^{*}$ and I want to go to the second solution $y^{*}$ with bases $B_2$, how to go to the second optimal solution through pivoting?
My attempt was trying to prove ...
0
votes
1answer
27 views
Linear programming - optimisation
I am being asked to give an explanation what happens if, when pivoting, we chose the right entering variables and the wrong leaving variables if we chose positive pivot element, and why?
and what ...
