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

Set up the dual and use complementary slackness conditions to find the optimal solution. The answer must be (-5) [closed]

strong text $Z=-3x_1-x_2$->min Subject to $4x_1-x2\geq 0$ $2x_1-x2\leq 0$ $x_1+x_2\leq 0$ $x_1,x_2\geq 0$
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
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
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
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 ...
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?
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 ...
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?
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
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}}$$ ...
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
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 ...
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.
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
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.
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 ...
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 ...
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 \...
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 ...
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 ...
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*} \...
0
votes
2answers
48 views

How to find a solution to an inequality system?

I need to find a solution to the following system of linear inequalities: \begin{align} x_1-x_2 &\le 1\\ x_1-x_4 &\le -4 \\ x_2-x_3 &\le 2 \\ x_2-x_5 &\le 7 \\ x_2-x_6 &\le 5 \\ ...
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-...
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
1answer
66 views

Why can't Simplex Method solve big equations? Have I forgot something?

I just wrote a Simplex Method in pure C-code and I have tested it. It works for the objective function: $$\max: c^T x$$ With subject to: $$Ax \le b \\ x \ge 0$$ Here is an example: ...
0
votes
1answer
16 views

Reformulation logical AND in integer programming maximization problem

Suppose we have variables $x_1,x_2,y \in \{0,1\}$ such that $y=1$ if and only if $x_1 = x_2 = 1$ and we want maximize the value of $y$. I know that this reduces to the following Integer programming ...
0
votes
0answers
26 views

Questions about Simplex method - How should I devide?

I have made a simplex method algorithm in C language and I have some questions about it. Assume that we have this objective function. $$max: z = c^T x$$ At the subject to: $$Ax <= b \\ x >= 0$$ ...
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
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
49 views

Prove in a $4 \times 4$ battleship game the expected payoff of player one is $\frac{3}{4}$

A battleship game is played on a $4 \times 4$ matrix, player one can place their domino(that takes up $2$ adjacent spaces) in one of $24$ places(There are $3$ places in each row and each column it can ...
0
votes
1answer
26 views

Maximisation of the absolute value of a linear function subject to bound constraints: Am I wrong?

I have the following optimisation problem: $\max |a_0 + a_1x_1 + \dots + a_nx_n |$ subject to bound constraints $\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u.$ According to this previous post ...
0
votes
0answers
19 views

Solve the following problem graphically

I have a small question here ... If the problem has constrain (=) like this $...4x+3y=1$. how to do it in the graph to get the region ... Overlooking the original point or not?
0
votes
0answers
25 views

Let A be an $m\times n$ payoff matrix of a two person zero sum game. If the avg entry in a column $\ge 5$. Show row player's expected winnings $\ge 5$

Let A be an $m\times n$ payoff matrix of a two person zero sum game. If the avg entry in a column$\ge 5$. Show that the row player's expected winnings $\ge 5$ I'm assuming the proof has to do with ...
-1
votes
1answer
32 views

Combination of AND OR in Linear Programming

I have three binary variables: $x,y,z$. I want to define $U$ as follows: $$U = x \wedge (y \vee z)$$ Following this, I have already tried defining $$yz = y \vee z$$ and then, doing $$U = x \...
0
votes
2answers
81 views

Can linear programming be used to solve Ax = b equations?

Assume that we have a system $Ax = b$ and we want to solve that with constraints. Can linear programming be used to solve the $x$ from $Ax = b$? Assume that we have the objective function $$max : ...
0
votes
1answer
19 views