Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
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 ...