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
1answer
909 views

An LP problem from David G. Luenberger's Linear and Nonlinear Programming book

Could someone help me to solve the following problem? A class of piecewise linear functions can be represented as $f(x) = Maximum (c_{1}^Tx+ d_{1}, c_{2}^Tx, \cdots, c_{p}^Tx + d_{p})$. For such a ...
0
votes
0answers
7 views

Limit Derivative of solution to linear complementarity problem at discontinuity

Consider the linear complementarity problem with $\mathbf{M}$ a $P$-matrix and a vector $\mathbf{q}$ with unknown $\mathbf{z}$: Find $\mathbf{z}$ such that $\mathbf{M}\mathbf{z}+\mathbf{q} \geq \...
1
vote
1answer
21 views

What are "4 possible cases for primal and dual linear programming problems"?

I am studying for my Linear Programming exam. One of the questions is "4 possible cases for primal and dual linear programming problems"? Neither of my mates knows what it is about. We've ...
-4
votes
0answers
49 views

Why do they say Vectors have Dual Nature? [closed]

Is it because Vectors can be represented as a point in space and also can be represented using an arrow..?
0
votes
0answers
34 views

Prove that a system $Ax>b$ (i.e. $(Ax)_i>b_i$ for each $i$) is solvable iff $uA=0,u\geq0,u\ne0$ imply $ub<0.$

Prove that a system $Ax>b$ (i.e. $(Ax)_i>b_i$ for each $i$) is solvable iff $uA=0,u\geq0,u\ne0$ imply $ub<0.$ I've managed to show that $(\Rightarrow)$ holds but don't know what to do with ...
-1
votes
1answer
34 views

simple linear programming problem with integer constraints

Given positive numbers $a, b, c, d, e$, how do I find the maximum value of $ax + by$ such that $cx + dy \leq e$ and $x, y$ are non-negative integers?
3
votes
2answers
2k views

Removing redundant linear constraints using Gaussian elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
0
votes
1answer
28 views

When is a pseudoinverse of a binary matrix non-negative? [closed]

In a binary matrix $A \in \{0,1\}^{n \times m}, n>m$ with linearly independent columns, when would its pseudoinverse $\mathbf{A}^{\dagger}$ be non-negative (i.e., $\mathbf{A}^{\dagger}\geq 0$)?
0
votes
1answer
22 views

Alternate approach to formulate this MIP

This is in concern to reformulating a previously formulated set of linear equations in my previous question: This is the link \begin{align} y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\ \...
3
votes
1answer
2k views

Find all optimal solutions by Simplex

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the ...
0
votes
1answer
22 views

Optimization problem for competition design

My question is about a particular constrained optimization problem, but the problem is motivated by a hypothetical. Motivating story: I'm organizing a competition where $n$ players will play $d$ ...
0
votes
0answers
20 views

Find scale factors to maximize images size

I have two images with dimensions $w_1 \times h_1$ and $w_2 \times h_2$ respectively. I want to display them in a screen of size $w_{screen} \times h_{screen}$. My goal is to resize those images with ...
0
votes
0answers
13 views

Transshipment problem with unbalanced demand and supply

Let's say we have: Two supply points - Houston and Dalas, which produce 160 and 200 products. Two transshipment points - Chicago and Los Angeles Two demand points - San Francisco and New York, which ...
0
votes
1answer
16 views

Duality theory in Linear Programming

How can I calculate the number of total variables and constraints (without counting variable domain constraints)? Required to derive the dual model. LP relaxation of a linear assignment problem is ...
2
votes
1answer
2k views

What is the objective function and constraints of this problem?

How to solve this problem? This is what I know so far. Let A be the no. of drivers at the beginning of the year. Let B be the no. of drivers fired. Let C be the no. of drivers recruited Is the ...
0
votes
0answers
12 views

How to implement waiting time in objective function time violation?

I would like to build an objective function for the vehicle platoon problem. the objective function called minimize time violation. vehicle platoon means trucks travelling in a straight line to reduce ...
1
vote
0answers
19 views

Linear Objective with quadratic constraint

Suppose $H$ is a symmetric positive definite matrix, and $h$ a vector. I want to solve the following optimization problem with linear objective and quadratic equality constraint: $$\underset{v^THv = 1}...
-1
votes
1answer
27 views

Weak Dual Pair Questions [closed]

I'm currently studying for my finals and I have been going over past exam papers and I do not know where to start where these 2 questions are concerned. Any advice or model solution would be highly ...
0
votes
0answers
14 views

Linear inequality system feasibility by column reduction

In the code in this thesis: Achim Flammenkamp "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers", Diplomarbeit an der Fakultät für ...
0
votes
0answers
33 views

Condition for no solution of system of linear inequalities?

Suppose I have the following system of linear inequations $A x \le b$ where $x \in \mathbb{R}^n$ and $A$ is an $n \times n$ matrix, $b$ is an $n \times 1$ vector. Are there some necessary and ...
1
vote
1answer
45 views

Converting this non-linear minimization problem to linear

My Problem: I would like to convert the following non-linear minimization problem into a linear programming problem, to solve it with the simplex method. The non-linear function could be of any shape ...
1
vote
1answer
45 views

Finding parameters of a linear programming problem

I have the following programming problem: $\min c_1x_1+c_2x_2$ such that $$x_2 \leq x_1$$$$x_1 \leq 2x_2+2$$$$x_1, x_2 \geq 0$$ How do I show that this problem is feasible and how do i find the ...
0
votes
0answers
13 views

Proving that if a certain problem has optimal solutions, then there exists an extreme point of $P$ that is optimal

Consider the problem of the form $\min\{f(x)| x \in P\}$ where $f : \mathbb{R}^n → \mathbb{R}$ is a concave function and $P$ is a pointed polyhedron. Prove that if the problem has optimal solution(s), ...
1
vote
2answers
431 views

Reading the primal solution from dual simplex tableau

I was following ptrickJMT's video on how to solve a minimization linear programming problem and he did something that I did not understand why it works. He starts with the following minimization ...
4
votes
1answer
2k views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
0
votes
0answers
20 views

How to maximize the dependent variable in a linear equation with fixed sum of independent variables?

I have a use-case where I need to use the linear equation to maximize the dependent variable ie Y in the linear equation, but the constraint is, the sum of independent variables ie xo, x1, x2, x3, x4 ...
0
votes
2answers
37 views

Find the inverse of a transformation

I am studying pure maths as a hobby. I am trying to understand inverse transformations. The text book I am using gives an example of how to do it: Find the inverse transformation $T^{-1}$ of $T:\begin{...
3
votes
2answers
90 views

Solving a linear system to infer damage values in an RPG

Background. In an RPG game, I've found that the weapon can destroy each object $i$ in a characteristic number of hits. When upgraded, the weapon can destroy each object $i$ in fewer hits. I am trying ...
2
votes
2answers
5k views

Hyperplane is a convex

I am not too sure how to prove that a hyperplane in $\mathbb{R}^{n}$ is convex? So far I know the definition of what convex is, but how do we add that hyperplane in $\mathbb{R}^{n}$ is convex? Thanks ...
0
votes
1answer
3k 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
930 views

Using simplex method to show that a linear program has no finite optimal solution

Suppose I was given a linear program like $$\max z = - x_1 + 2x_2 + x_3 $$ s.t. $$ 3x_1 + x_2 - 4x_3 \leq 4$$ $$x_1 - x_2 - x_3 \leq 10$$ $$x_1 - 2x_2 + 6x_3 \leq 9 $$ $$x_1, ...
0
votes
2answers
34 views

Reformulate IF-statement in mathematical optimization

I have an optimization problem that chooses which location must be opened based on a set of possible locations. And per location we have a certain amount of available spots from which we must buy a ...
-1
votes
1answer
27 views

Show the set of symetric postive semidefinite is a cone in $\mathbb{R}^{n\times n}$ [closed]

Show the set of postive semidefinite symetric ${n\times n}$ matrices is a cone in $\mathbb{R}^{n\times n}$ Let $\mathbb{S}{+}^{n}$ be the set of semidefinite symetric ${n\times n}$ matrices so by ...
0
votes
0answers
22 views

Problem on duality simplex algorithm

Consider the linear programming $\{cx|Ax=b,x\geq 0\}$, We say a basis of $A$ is dual feasible basis if $c-c_BB^{-1}A \geq 0$. Then, I want to show that the dual feasible basis exists if and only if ...
2
votes
1answer
58 views

Prove a feasible point is optimal for an LP using complementary slackness

Prove that $(2,0,0)$ is the optimal solution to this problem. P) Minimize $2x_1+5x_2+7x_3$ subject to constraints: $7x_1+6x_2+3x_3-s_1=14$ $2x_1+4x_2+5x_3+s_2=4$ Where: $x_1,x_2,x_3 \ge 0$ This ...
0
votes
0answers
34 views

Establish constraints

This question is based on this. There are two equations given as solutions by prubin. However, now I want something different. I want the first constraint to ensure that at least $a$ out of the first $...
1
vote
1answer
106 views

vector subset problem for linear approximation

Let $V = \{v_1,v_2,..,v_n\}$ be a set of vectors in $\mathbb{R}^n$, $t$ be the target vector in $\mathbb{R}^n$ and a natural number $m > 1$. Properties about $V$ and $t$: $cos\phi(t,v_i) \geq \...
0
votes
1answer
1k views

How to convert linear program into standard form?

Suppose I wish to solve the linear program $$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\ & x > 2016\end{array}$$ where $x>2016$ means that all ...
2
votes
2answers
1k views

How get the extreme directions of an unbounded feasible region

The following constraints form a feasible region. $-x_1+x_2 \le 2$ $-x_1+2x_2 \le 6$ $x_1,x_2 \ge 0$ The feasible region have three extreme points: $e_1=\left[\begin{array}{cc} 0\\ 0 \end{...
2
votes
0answers
30 views

Solve linear system with absolute value constraint

I have a linear system of equations $$A(\xi)x(\xi)=b(\xi),$$ where $\xi \in \mathbb{R}_+^1$ is a parameter, $A\in\mathbb{R}^{N\times N}$ and is non-singular, and $x,b \in \mathbb{R}^N$. I would like ...
1
vote
1answer
31 views

Dual Linear Program

I was asked to construct dual linear program to prove the following statement: $S_1=\{A^Ty\leq0, b^Ty>0\}$ is nonempty iff $S_2=\{Ax=b,x\geq0\}$ is empty. I'm trying to begin with $$\min_{A^Ty\geq0}...
1
vote
2answers
47 views

What is the best way to check if data is inside constraints? Linear programming?

Assume that every black line can be displayed on this linear equation. Let's define them as constraints. $$y = Kx + M$$ where $K$ is the slope and $M$ is the bias. The purple is my data. My goal is to ...
0
votes
0answers
39 views

how to build mathematic formulation for time violation?

I build a mathematical model to find a multi-objective model for the vehicle platooning problem. I am using the Gurobi optimization tool to build a mathematical model. The problem I am facing: Create ...
0
votes
0answers
21 views

Where is the reduced cost on the simplex tableau?

I've seen simplex tableau that looks like: $$ \begin{bmatrix}\underline 0 & A & \underline b\\ 1 & -\underline c^T & 0\end{bmatrix} $$ which corresponds to to the problem of minimzing $...
0
votes
1answer
33 views

Partial conditional constraint in mixed integer linear program

I have an integer parameter $\rho$, and 2 variables, $g$, which is a matrix of binary variables of shape $(m, t)$, and $x$, which is a list of binary variables of shape $t$. I want to formulate a ...
1
vote
1answer
29 views

Obtaining the dual optimum from the primal optimum

I'm developing a program which repeatedly needs the dual optimal of a certain linear programming problem. There is a fast algorithm to obtain the primal solution and I want to use this primal solution ...
0
votes
1answer
52 views

How to convert non-linear equation to linear equation [closed]

I have a problem with X machines, each one with a specific production. All the production needs to be sent to an specific place via different routes which may or may be not cheaper. I need to minimize ...
12
votes
1answer
8k views

Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question. I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have $...
0
votes
1answer
47 views

Inferring dimension of a polyhedron from a point

If we have a polyhedron $P = \{x\in\mathbb{R}^n \mid Ax \leq b \}$, and we find a point $x\in P$ such that $x$ satisfies at least $n$ of the $Ax\leq b$ (linearly independent) inequalities strictly, ...
0
votes
0answers
13 views

feasible region of $\text{min} \;\;\; z= \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}$ and the set of its recession directions

Show that the following LP always does have an optimal solution $$\text{min} \;\;\; z= \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}$$ $$\text{s.t.} \;\;\; \sum_{j=1}^{n} x_{ij}=a_i,i=1,...,m$$ $$ \;\;\;...

1
2 3 4 5
90