Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
3,561
questions
1
vote
1answer
26 views
Suppose a two digit whole number is divided by the sum of its digits, largest and smallest possible values
Suppose a two digit whole number is divided by the sum of its digits, what are the largest and smallest possible values?
So we can write a two digit whole number as $n = 10a+b$ where $1 \leq a,b \leq ...
0
votes
0answers
45 views
Solving Ax=b with matrices (bigger than 2 by 2 matrices)
I have been working on creating a program that solves linear systems of equations for the Jacobi and Gauss-Seidel iterative methods. (Link to the methods: https://www.cis.upenn.edu/~cis515/cis515-12-...
1
vote
1answer
18 views
How to solve linear equations with structured matrices?
Suppose $\mathbf{x}\in R^{m\times 1}$, $\mathbf{X} = [\mathbf{x}\, \mathbf{x}\, \cdots]^\top\in R^{nm\times 1}$ and $\mathbf{b}\in R^{nm\times 1}$ and $\mathbf{A}\in R^{nm\times nm}$. How to solve
\...
0
votes
0answers
20 views
Linear independence and simplex
Let $X:=\{x \in R^n |Ax=b \}$ and $I \subset \{1,...,n\}$ such that, $b\in C([\{a_i\}_{i \in I}$]). Prove that for every set $B \subset \{1,...,n\}$, such that $\{a_i\}_{i \in B}$ is linearly ...
0
votes
1answer
30 views
Optimize absolute value $\min |x| + |y|$
How do you convert $\min |x| + |y|$ to a linear program?
Is this method correct?
$$\min w + z$$
$$w >= x$$
$$w >= -x$$
$$z >= y$$
$$z >= -y$$
0
votes
0answers
15 views
Prove that the Basis Solutions of a Linear Programming Problem are the Extreme Points of the Polyhedron of Allowed Solutions
Given a system of
$$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$
where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean ...
2
votes
1answer
44 views
Show that if Phase I of the two-phase method ends with an optimal cost of zero then the reduced cost vector will always take the form $(0, 1)$
Consider a linear programming problem of the form:
minimize $c^Tx$
subject to:
$Ax=b$, $x\geq0$
where $A$ is an $m\times n$ matrix with linearly independent rows. Show that if Phase I of the
two-...
0
votes
1answer
48 views
An Application of Farkas' Lemma
The Farkas' lemma I know is:
Exactly one of the following systems has a solution.
\begin{equation}
\left\{
\begin{array}{l}
Ax=b,\ x\geq0 \\
A^Ty\geq0, \ y^Tb<0
\end{array}...
0
votes
0answers
13 views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
1
vote
1answer
45 views
Formulate the mathematical model to find the optimal solution
A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
1
vote
1answer
25 views
deciding to insert a variable a to the basic set in the next step and exclude 𝒂 basic one 𝒃
Let's say you are in the middle of applying the Simplex Method to an LP problem. You've reached a tableau and by checking the sign of the objective coefficients you decided to insert a variable a to ...
0
votes
0answers
17 views
LPP: Simplex Method - Interpreting Solutions
Having trouble keep all the cases straight in my head for the Simplex method in Linear programming problems.
What does it mean for a Simplex table solution to be feasible but not optimal? Both ...
1
vote
0answers
25 views
Find the lowest difference in exchanged value
I was wondering if this type of problem can be modelled with Linear Programming or any other approach that much more efficient.
Let say I've 5500 in original currency. I want to convert to other ...
1
vote
0answers
38 views
Linear transformation of overdetermined linear system
Assume that we have the following over-determined linear system
\begin{cases}
z_{1}=c + \phi z_0\\
z_{2}=c + \phi z_{1}\\
\dots\\
z_{n} = c + \phi z_{n-1}
\end{cases}
with $n>2$ and all $z_{0}, \...
0
votes
0answers
28 views
Linear programming such that feasible solution gives optimal solution to another
Let us say that we have a linear program $P={ (min C^tx | Ax=b,x\geq0)}$
Assume that $(P)$ has an optimal solution. Write a system of linear equations and inequalities $(P_1)$ such
that any feasible ...
1
vote
1answer
20 views
Minimizing a General n-Dimensional Linear Program
I am currently studying linear programming and am attempting to solve:
minimize $c^Tx$
subject to $\sum_{i=1}^{n}x_i=0$, and $\sum_{i=1}^{n}x_i^2 = 1$.
From the second constraint I know that: $-1\...
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
17 views
Find $y \in \operatorname{conv}(\{x_{1}, x_{2}\})$, so that $z \in \operatorname{conv}(\{y, x_{3}\})$
Let $z \in \operatorname{conv}(\{x_{1}, x_{2},x_{3}\})$. Find $y \in \operatorname{conv}(\{x_{1}, x_{2}\})$, so that $z \in \operatorname{conv}(\{y, x_{3}\})$
My idea so far: since $z \in \...
0
votes
0answers
29 views
How to show that the lpp has optimal solution without solving it
I have got to maximize $$Z=x+2y-3z+4w$$
subject to constraints
$$x+y+2z+3w=12$$
$$y+2z+w=8$$
$x,y,z,w\geq 0$ .
The question asks to show without actually ...
1
vote
1answer
28 views
Linear program with unknown constraints(just extreme points)
Suppose you are given a set $F$ consisting of $n$ mutually distinct bounded points in $\mathbb{R}^d$. We can define a linear program
\begin{align}\max \ c^Tx \\\text{s.t.}\ \ x \in \text{Hull}(F)\...
0
votes
1answer
48 views
Cannot Understand solution: Inconsistent systems of linear inequalities proof.
I'm trying to understand the solution to this question in Bertsimas 4.29:
Question: Let $a_1,....a_m$ be some vectors in $R^n$ with $m>n+1$. Suppose that the system of inequalities, $a_i'x \geq ...
3
votes
1answer
90 views
Null Variable in linear programming
Let $P=\{x\in\mathbb{R}^n|Ax=b,x\geq0\}$ be a nonempty polyhedron, and let $m$ be the dimension of the vector $b$. We call $x_j$ a null variable if $x_j=0$ whenever $x\in P$.
(b) prove that if $x_j$ ...
1
vote
0answers
49 views
Simple Linear Algebra/ Linear Programming Proof: Proving Existence of Vector that satisfies Properties
Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $x_j$ is ...
1
vote
0answers
69 views
Maths (ILP) puzzle from a programming contest
This programming contest puzzle concerns itself with "cards", each of which bears a certain pattern of either one circle, one square, one triangle,
two circles, two squares, etc. up to three circles, ...
0
votes
1answer
57 views
Two conditional constraints (either or neither) for integer binary programming [closed]
Not sure how to go on about finding this constraint. The constraint asks for; either both or neither of $x_1$ and $x_2$ should appear.
What I have so far is that y can be either binary values $0$ or ...
0
votes
0answers
8 views
How to prove that $c^Tx(\mu)$ is strictly decreasing with $\mu$ in interior point method for LP
Consider the Primal-Dual problem,
(P)min $c^Tx$
s.t. Ax = b, x $\geq 0$
(D) max $b^Ty$
s.t. $A^Ty + s = c$, s $\geq 0$
The log-barrier function for (P) is :
min $c^Tx - \mu \sum_{i=1}^n ln(x_i)...
2
votes
2answers
48 views
Formulating Linear Program: Separating Hyperplane
Consider a polyhedron $P$ that has at least one extreme point.
Suppose that we are given the extreme points $x^i$ and a complete set of extreme rays $w^j$ of P. Create a linear programming problem ...
1
vote
2answers
92 views
check for a compact set
How to prove this
$$S = \{(x, y) | Ax + By ≥ c, x ≥ 0, y ≥ 0\}$$
where $A$ is an $m \times n$ matrix, $B$ is a positive semi-definite $m \times m$ matrix and
$c \in \Bbb R^m$. The author explicitly ...
0
votes
0answers
15 views
prove max min = min max for linear programming
i guess this problem has something to do with duality, can someone please give me an intuition
problem of min max = max min
0
votes
1answer
36 views
Maximize a piecewise function
I'm trying to linearize the problem:
$\max f(x)\\\text{s.t.}\\g(x)\geq 0$
Where $g(x)$ are already linear functions, but $f(x)$ is the following piecewise function:
$f(x)=\begin{cases}
bx, & \...
1
vote
0answers
31 views
Real World Example for Linear Programming in Finance
I am studying operations research and have been researching real world problems/applications of such things as linear programming, integer programming, MIP ect. I found mostly complete problems in my ...
0
votes
0answers
34 views
Formulating a pipeline with several variables
The question
I have one constraint as number of faculty signing a contract of length r, i am unsure what other constraints i can make to complete the program. Would it be the amount of years worked?
1
vote
1answer
70 views
Breakdown an integer value to an array of integer maintaining the sum
I am working on a project where I need to breakdown an integer value according to an array of percentage values.
My end array must contain integer value and the sum of the array must be equal to the ...
0
votes
1answer
44 views
Number of $x \in [0,1]^n$ such that Ax integer
If $A$ is an integer matrix in $\mathbb{Z}^{m \times n}$, why is there only a finite number of vectors $x \in [0,1]^n$ such that $Ax$ is a vector of integers?
0
votes
1answer
31 views
Reduce integer linear program constraints
I currently have defined a pure integer linear program that works well, but the number of constraints for a given input runs out of time and/or memory. Let me introduce the problem.
I have an ...
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
1answer
30 views
Task Selection Problem
I am trying to distribute 15 tasks to two people. Each task can only be assigned to one person and each person has a time budget.
I want to express this problem as a linear program (ultimately in the ...
0
votes
0answers
8 views
Why is it necessary for the RHS values in constraints to be non-negative for the Simplex Method?
What logical problems arise with negative RHS value in constraints? What does the presence of negative RHS mean, in a real-life example?
0
votes
0answers
45 views
Finding Dual Objective
I have the following simplified optimization problem:
$max \quad ax+by$
S.t.
$0≤x≤\bar{X}$
$0≤y≤\bar{Y}$
$z=E−x+β.y$
where, $E$, $β$, $a$, $b$, $\bar{X}$, $\bar{Y}$ are parameters and the rest ...
0
votes
0answers
19 views
How can I reformulate the problem in terms of convex combinations of the extreme points?
Maximize $$ x_1 + 2x_2$$
\begin{align} x_1 - 4x_2 &\le 4 \\
-2x_1 + x_2 &\le 2 \\
-3x_1 + 4x_2&\le 12 \\
2x_1 + x_2 &\le 8 \end{...
0
votes
1answer
18 views
How to correctly formulate multiple constraints to multiple feasible regions into one?
I believe this is a linear programming question that basically boils down to correctly formulating a feasible regions constraints from OR statements between other feasible regions.
My direct question ...
0
votes
1answer
24 views
Is this conditional sum function valid for linear programming?
Linear programming requires a linear function to maximize in order to operate properly.
I am trying to figure out whether I could use linear programming to solve a problem. However, I would need a ...
0
votes
0answers
33 views
Is strict complementary slackness unique?
We have $A \in \mathbb{R}^{m \times n}$ and rank$(A)=m$.
By strict complementary slackness, we know that if the primal $(P)$ (in standard equality form) has an optimal solution, then the dual $(D)$ ...
0
votes
0answers
27 views
Prove there exists unique partition of a matrix
We have a matrix $A \in \mathbb{R}^{m \times n}$ and rank$(A)=m$.
Prove that there exists unique partition $[B(A), N(A)]$ of $\{1,2, \dots, n\}$ (the columns of $A$) such that there exist $\bar{x} \...
0
votes
0answers
24 views
Min max of quadratic function
$$\min_{x \in \mathbb{R}^n} \max_{1 \leq i \leq k} \frac 1 2 x^T Q_i x + b^T_i x + c_i$$
$$Ax = d$$
$Q_i$ are positive definite matrices. Find dual problem.
I found out that this problem called ...
0
votes
0answers
32 views
Find the largest $\epsilon$ for any $0\le t\le \epsilon$ s.t. $\vec x^*$ is still optimal to the given LP
Maximize $\vec c*\vec x$ subject to $A\vec x\le \vec b$ and $\vec x \ge \vec 0$
$\vec c$=$\begin{bmatrix}1 \\2\\1\end{bmatrix}$, $\vec x$=$\begin{bmatrix}x_1 \\x_2\\x_2\end{bmatrix}$
A=$\begin{bmatrix}...
0
votes
0answers
78 views
Linear programming example need help
***I'm new here I have one example of linear programming so if you can point me in the right direction.
Here is the text of exercise:
The company manufactures two-unit home air conditioners, which ...
0
votes
0answers
50 views
complexity of linear programming
I am analyzing the computational complexity of an algorithm that includes as a step the solution of a linear subproblem of n variables and n constraints.
The linear subproblem can be solved by the ...
1
vote
1answer
24 views
Writing different constraints using equivalent variables
Let $z_{ij}\in\{0,1\}$ be a binary variable and $t_{ij}\geqslant0$ be a continuous variable. I have the following equivalence: $$z_{ij}=1\iff t_{ij}>0.$$
Since we have an equivalence between $z_{...
0
votes
0answers
25 views
Linear Regression's Indicators method
So I have a general multiple linear regression model as the following:
$$
y_i = \alpha_0 + \alpha_1z_i + \alpha_3w_i + \alpha_{13}z_iw_i + \epsilon_i,\quad \epsilon_i\sim N(0,\tau^2).
$$
where $z_i ...
