Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

Filter by
Sorted by
Tagged with
2
votes
0answers
15 views

Theta-Ratio of a Simplex Method for a degenerate solution, are they always equal?

Are the $\theta$-ratios of two degenerate solutions always equal? So as to say: If we know two unique points yield the same objective value, must their $\theta$-ratios always be equal? For two ...
0
votes
0answers
13 views

Special Case of the Two Phase-Method

I'm sorry this question must be slightly vague. In the two-phase method, my general understanding is that you try to exit your Aritifical Variables to make your Auxillary problem to $0$. But what ...
0
votes
0answers
30 views

Linearize nonlinear equality [closed]

Is there any way to linearize following equality for using Lp solvers in an optimization problem? $x-x^2=0$
1
vote
1answer
19 views

Linear Programming Price Change After X Units Sold

I have a question regarding writing some formulas for LP. How would you code the price change after X number of units sold. So lest say the base price for the first X units sold is £5 and then there ...
0
votes
1answer
34 views

Prove that exactly one of the systems has a solution

Let $A$ be an $m$x$n$ matrix, $B$ $l$x$n$ matrix and $c\in R^n$. Prove that exactly one of the systems has a solution: i)$$Ax\leq0,\:\: Bx=0,\:\: c^Tx>0,\:\: x\in R^n$$ ii)$$A^Tp+B^Tq=c,\:\:p\geq0,...
1
vote
1answer
31 views

Linear Programming problem of accepting reservations on different fare classes to maximize revenue

this question has my stuck, I am unsure on how to incorporate the some of the information into constraints and without them the answer seems a bit silly. Below is the question, please let me know how ...
1
vote
1answer
830 views

Algorithm for Finding the Extreme Rays of a Polyhedral Cone

I would like an algorithm for the following problem: Given: a finite set of vectors $\{\mathbf v_1, ... , \mathbf v_n\} \subset \mathbb R^N$, Find: the extreme rays of the cone \begin{equation} C = ...
2
votes
0answers
43 views

Merging two line equations having similar angle into a new one [duplicate]

I would like to merge two lines having a y = mx + b equation with very close angles. I am simply comparing their angle difference, then I create a new line passing ...
-4
votes
0answers
21 views
0
votes
0answers
6 views

what pivot should I choose when introducing new constraint trying to apply the Dual Simplex Method and all $b_i$ are positive?

There is an LP. It is already given that $x_1 = 0, x_2 = 1$ is the optimal solution. First I find the corresponding simplex tableaux. Then what I don't get is how to apply the dual simplex method when ...
1
vote
1answer
24 views

Asked to find the dual of a given primal problem. (Is my solution wrong? Solutions included)

I'm not understanding how there can be two separate solutions to this problem. I've doubled checked and followed all the steps but I'm assuming my answer is wrong but similar? Sorry, I don't have ...
0
votes
1answer
70 views

A question on algebraic inequalities [closed]

Given \begin{align} X+Y&\leq C_1\\ Y+Z&\leq C_2\\ Z+X&\leq C_3 \end{align} Find the maximum of $X+Y+Z$, where $X, Y, Z$ are non-negative integers and $C_1, C_2, C_3$ are positive ...
1
vote
0answers
20 views

Local branching in Benders Decomposition

I am trying to understand how local branching is used in Benders Decomposition. I was wondering if someone could kindly explain me how exactly local branching works. If my understanding is correct, ...
0
votes
0answers
22 views

Using the Two phased simplex method solve this problem [closed]

Maximise 10.168x(a)+38.942x(b)+100.323x(c) subject to 2.71x(a)+5.48x(b)+8.88x(c)= 5.91 x(a) + x(b) + x(c) =1 x(a), x(b), x(c)≥ 0
0
votes
0answers
27 views

Need help formulating this linear program

A company's pension fund manager must invest a maximum of $300,000 in bonds and stocks in order to obtain the highest possible return on investment. However, in order to obtain a risk-adjusted ...
2
votes
0answers
20 views

In a Linear Programming Problem, how is Degeneracy affected by the number of variables and constraints?

In an LPP, with m constraints and n variables. How does the number of constraints and variables affect the degeneracy of the system?
1
vote
1answer
28 views

Verify that the optimal basis consists of the particular slack variable without using simplex method.

In a linear programming problem, how to verify that the optimal basis consists of the slack variable of a particular constraint without using the simplex method? Consider the following problem: $$ {\...
2
votes
1answer
854 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
0answers
19 views

Objective function change

(So i was trying to find how to allocate my stats in my rpg character and i stumble across something i don't know how to formulate): Maximize $$Z = \frac{x_1}{100}*\left(1+\frac{x_2}{100}\right)*(...
0
votes
1answer
49 views

Rewrite as second order cone constraint

Can someone please explain how to convert the following into a second order cone programming formulation: $\{(x,y,z,w,u): x,y,z,w \geq 0, (xyzw)^{\frac{1}{2}} \geq ||u||_2^2\}$ $\{(x,y,z,w,u): x,y,...
0
votes
0answers
14 views

Parametric linear programming - range of optimal parameters

Consider the following LP: minimise $(c+\theta d)^T x$ s.t. $Ax = b+\theta g$, $x \geq 0$ Suppose that $A$ has full row rank and the corresponding basis matrix $B$ are optimal for the parameter ...
1
vote
1answer
19 views

Find average value of the function $f(x,y,z)=3x-4y+5z$ over the triangle (simplex) $x+y+z=1$ ($0\leq x,y,z<1$).

Find the average value of the function $$f(x,y,z) = 3x-4y+5z$$ over the triangle (simplex) $\left\{ (x,y,z) \mid x+y+z=1 \land 0 \leq x,y,z < 1 \right\}$. Is there a simple way to do this problem?
0
votes
1answer
1k views

Ratio Calculation in Linear Programming?

i struggle a bit with ratio and fraction calculations, so im just looking for some explanation for dummies of this one. in linear programming, i have a ratio constraint of 6:5, of product A to ...
0
votes
1answer
49 views

3d permutation matrices

$8 \times 8$ permutation matrices correspond to patterns of 8 rooks on a chessboard with exactly 1 rook in each row or column, never 2. Consider patterns of $n^2$ "3d rooks" in an $n \times n \times ...
2
votes
0answers
29 views

Chebyshev approximation and linear programming

I'm trying to do the problem below and I cannot understand what (ii), (iv) and (v) are asking for. From my understanding, Chebyshev approximation is used to transform a norm approximation ...
0
votes
0answers
21 views

Optimal choice of matrix element subset

Let's suppose that we have an $n \times n$ matrix $M$ containing only strictly positive elements $m_{ij}$. Is there a fast algorithm/procedure that finds the subset of elements $$m_{i_{\nu}j_{\nu}}$$ ...
1
vote
2answers
32 views

How to do regularization in linear programming

For quadratic programming, the trick can be implementing an constant. Example: $$H = A^T Q A$$ $$Min: \frac{1}{2}x^THx + c^T x$$ Where $Q = \alpha I$ This gives more smooth optimal values. Just ...
0
votes
1answer
41 views

Determine the function is convex function or not?

I've got some trouble in determining the function, which contains vectors and matrix, is a convex function or not. \begin{aligned}\min _{x}k^{T}x\\ s.t. Ax\leq y\end{aligned} $x$ is $n\times1$ ...
0
votes
0answers
24 views

linear regression-positive answers

Assume we have an over-determined linear system as $Mx=y$. We know that this system has infinitely many solutions. In case the variables($x$) are free in sign, we can find a solution to this system ...
0
votes
1answer
377 views

Least Absolute Deviation (LAD) with Non Negative Constraint

I would like to solve the following: $$ \begin{align} \text{minimize} & \quad & \left\| A x - b \right\|_{1} \\ \text{subject to} & \quad & x \succeq 0 \end{align} $$ What kind of ...
0
votes
1answer
22 views

what is Explicit And Implicit Qr Algorithms For Symmetric And Non-symmetric Matrices?

I thought that QR algorithm decomposes a matrix into an orthogonal matrix Q and a upper triangular matrix R using GramSchmidth process for singular matrices but, what is meant by Explicit and ...
1
vote
1answer
56 views

Derivative of the solution of a linear program

Let $x^\star$ be a solution of the linear program \begin{align} \text{maximize} &\quad c \cdot x \\ \text{subject to} &\quad A \cdot x \leq b \end{align} How can one compute the derivatives of ...
0
votes
0answers
20 views

Find optimal solution from given a basic solution?

Let the program linear : $MaxZ=5x+4y+7z$ Subject to : $3x+8y+2z≤40$ $9x+5y+7z≥35$ $7x+3y+3z≥51$ $x,y,z≥0$ Then given a basic solution $x^{*}=(4,2,6)$ Question is : Find optimal (...
0
votes
0answers
26 views

Can vector partitioning be done with real-valued weighted vectors?

Given a set of $n$ real-valued vectors $V$ with $v_i \in \mathbb{R}^d$ for $1 \le i \le n$, I am wondering if it is possible to find a partitioning $V_1, V_2$ such that $|\sum_{i=1}^{|V_1|} \sum_{j=1}^...
1
vote
0answers
32 views

Making Matrix Totally Unimodular

Is there a way I can rewrite the following matrices to make the matrix (A) to be totally unimodular and still maintain the relevance of the equations. Thanks.
2
votes
2answers
4k views

How to minimize a sum of absolute values using linear programming?

I am having trouble understanding the logic behind optimization of cost function of the form $$\min (|x| + |y| + |z|) \,$$ subject to constraints $$Ax \le b \qquad Cx = d $$ such as $$ x + y \le 1 \...
-1
votes
1answer
221 views

Find all the points satisfying the Fritz John conditions

Consider the problem $$\min \>x^2+y^2 $$ $$s.t.\> x^2-(y-1)^3=0$$ Find all the points satisfying the Fritz John conditions Solution The FJ conditions are $$2x+\mu_1 2x=0$$ $$2y-\mu_1 3(y-1)^...
0
votes
0answers
21 views

Optimization Using KKT Conditions

I need to maximize the profit function π=50x+10y subject to the constraints x,y≥0 and x-y≤3 and 5x+2y≤20 using KKT conditions.
0
votes
0answers
21 views

Lagrange duality for the binary linear programming.

I've obtained a linear programming formulation for the following problem. There are $N$ mouses and $N$ keyboards. Denote the performance of forming a set of both $i$-th mouse and $j$-th keyboard, say ...
1
vote
1answer
720 views

How to Formulate the given Linear programming program

Chemlabs produce the domestic cleaning solutions $A$ and $B$ by processing the raw materials for $I$ & $II$. The processing of $1$ unit of raw material $I$ costs $\text{Rs. }80$ and produces $0.5$ ...
1
vote
2answers
74 views

Formulation for IP of large OR statement which gives a good linear relaxation

Let $N$ be a very large number. I want a good way to program that $x$ should be one if and only if one of $x_i$ is equal to one.We can write the following Integer Programming problem: \begin{align*} \...
1
vote
0answers
66 views

Can the following be expressed as an LP with (an) additional constraint(s)?

Using Gurobi, I am trying to solve the following LP $$\text{minimize} \sum_{i=1}^d r_i \\ \text{subject to } x^TV - r = 0 \\ -1 \le x_j \le 1 \text{ for all } 1 \le j \le n $$ Here, $V$ is a set of ...
2
votes
2answers
39 views

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$. Hi so I dont know if this is true or not, ...
0
votes
2answers
19 views

Linear programming - Standard form with variable restricted from both sides

I have a pretty straightforward linear programming problem here: $$ maximize \hskip 5mm -x_1 + 2x_2 -3x_3 $$ subject to $$ 5x_1 - 6x_2 - 2x_3 \leq 2 $$ $$ 5x_1 - 2x_3 = 6 $$ $$ x_1 - 3x_2 + 5x_3 \...
3
votes
2answers
189 views

Need help defining a Quadratic Programming problem

I have an optimization problem which should be solvable with Quadratic Programming: There are $n$ multiplication coefficients $c_i$ for which optimized values are searched. The coefficients are ...
0
votes
0answers
17 views

How to find the $K$-nearest neighbor vertexs in a polyhedron defined by a set of linear inequalities?

Consider a polyhedron $\mathcal{P}$ defined by a set of linear inequalities, i.e., $$\mathcal{P} = \left\{ x \in \{0,1\}^N \mid Ax\le b \right\}$$ Suppose $\mathcal{P}\neq \emptyset$. If I have a ...
1
vote
1answer
747 views

Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
0
votes
1answer
81 views

How to find the general solution set to a constrained system of linear equations

Consider the following general system of linear equations $$ \begin{pmatrix} a & -b\\ -c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} v \\ w \end{pmatrix} $$ where $...
0
votes
1answer
16 views

Binary Matrix with constant row and column sum contains a permutation matrix

The following problem was given as a homework problem, so I am not necessarily asking for a full solution, but rather a good hint on where to start. A chess board, where some of the $64$ cells ...
0
votes
3answers
41 views

How to solve a system of linear inequalities?

I am working on the following exercise: Find a solution to the following system or prove that none exists: \begin{align} x_1-x_2 &\le 4\\ x_1-x_5 &\le 2\\ x_2-x_4 &\le -6 \\ x_3-...