Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...