A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
9 views

How to match my toy problem to primal dual explanatory formulas?

I am trying to understand weak and strong duality given a toy example LP program, which is to: maximize $m_D$D + $m_L$L s.t. 0.3 L + $\ \ \ \ \ \ \ \ $D $\leq$ 1 $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...
2
votes
0answers
246 views

Prove that a convex polytope has finitely many extreme points.

$a)$ Prove that a convex polytope has finitely many extreme points. $b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope. Hint : what are the ...
0
votes
0answers
17 views

Locating extreme points graphically

$$\begin{array}{ll} \text{minimize} & x_1+2x_2+x_3\\ \text{subject to} & 3x_1+3x_2+x_3\ge3\\ &x_1+x_2+x_3\le2\\ & x_1,x_2,x_3\ge0\end{array}$$ For the given linear programming problem,...
0
votes
2answers
896 views

Problem regarding a LPP can have a non-basic optimal solution

Which on of the following statements TRUE? $(A)$ A convex set cannot have infinite many extreme points. $(B)$ A LPP can have infinite many extreme points. $(C)$ A LPP can have exactly ...
0
votes
1answer
20 views

Prove that a line is a polyhedral set (can be made by a finite number of inequalities)

I know that to prove this I have to shown that a set of finite inequalities make a line in $\mathbb R^n$ that is $$ L = \{ x_0 + \lambda d : \lambda \in \mathbb R^n \} $$ But can we say a line ...
1
vote
0answers
14 views

Defining binary variables on box constraints in mixed integer linear/convex program

I have $n$ variables $y_1,\dots,y_n\in\mathbb R$ with no upper bound and no lower bound. I want to define a binary variable $b\in\{0,1\}$ on condition that $b=1\iff \wedge_{i=1}^ny_i\in[0,1]$. How ...
2
votes
0answers
46 views

Linearize if-then constraints

For continuous variables $x$ and $y$, the constraints are: ...
0
votes
1answer
872 views

Formulation of mutually exclusive condition

So I have two integer variable and they can be one of the following $x=0, y=1$ $x=1, y=0$ $x=2, y=0$ how can I formulate this as an integer program? I've gotten $x + y \le 2$ and $y \le 1$ but ...
1
vote
2answers
68 views

Why can't the dual and primal linear program both be unbounded?

I know if a dual is unbounded then the primal is unfeasible and vice versa, but I don't know why they can't both be unbounded. Is it because it's impossible to have linear constraints that are ...
1
vote
1answer
1k views

condition for having a positive solution to a linear equation.

Let $Y$ be a member of $\mathbb{R}^m$. I need a necessary and sufficient condition on a $n\times m$ binary matrix $A$ for having a solution to the linear equation: $$AX=Y$$ Such that $X_i\geq 0$, $\...
1
vote
0answers
27 views

Difficult discrete optimization “knapsack” type problem [duplicate]

Take a bounded domain $S$ in which an explosive device is located. A team is deployed to find and disable the device before time $t^{*}$, when it will explode. There are certain constraints in place....
0
votes
0answers
35 views

Both primal and dual have a unique optimal solution. Something wrong in the assumption/theorem/example?

The answer here mentioned a table from Sierksma's $\textit{Linear and Integer Programming: Theory and Practice}$, Volume 1, page 144. Both primal and dual are under standard form in table below (Here ...
0
votes
1answer
59 views

How can I solve this linear optimization problem?

I've come across a question which I was not able to solve I would appreciate if someone could help me out here. Q) Given the constraints, $$x \ge 0$$ $$y \ge 0$$ $$x + y \le1$$ which of the ...
1
vote
0answers
18 views

Upper bound of convergence of ellipsoid mathod

Actually, I am looking for a tighter upper bound for $(1+\frac{1}{n^2 - 1})^{n-1} (\frac{n}{n+1})^{2}$. It is easy to prove $(1+\frac{1}{n^2 - 1})^{n-1} (\frac{n}{n+1})^2 < e^{-\frac{1}{n+1}}$. ...
0
votes
0answers
71 views

Does $A x > b$ have a solution?

Formulate a linear program that will determine whether or not $Ax>b$ has a solution, where $A$ is an $m \times n$ matrix and $b$ is an $m$-vector. We were told to use Farkas Lemma, but are not ...
0
votes
0answers
16 views

Nested Linear Program [duplicate]

I have a linear program: minimise $f^T x$ with equality and inequality constraints. This does not have a unique solution, so I would like to find the solution of this that also minimises $g^T x$. ...
1
vote
1answer
40 views

Rostering problem - variation of the post office problem

Suppose I have $N$ staff members. I employ each of them for 5 days during the week. Each day, $i$, from Saturday to Friday requires $s_i$ staff members. I wish to maximize the number of staff who ...
1
vote
0answers
34 views

Perturbation approach to lexicography in Linear Programming

Consider a standard form problem, under the usual assumption that the rows of $\textbf{A}$ are linearly independent. Let $\epsilon$ be a scalar and define $$\textbf{b}(\epsilon)=\textbf{b}+\begin{...
0
votes
2answers
2k views

Linear Programming Word Problem With 3 Variables

A company makes three types of candy and packages them in three assortments. Assortment I contains 4 sour​, 4 lemon​, and 12 lime ​candies, and sells for ​$9.40. Assortment II contains 12 sour​, 4 ...
2
votes
4answers
1k views

Can a linear program have strict inequalities?

In all linear programs I have seen so far, the constraints are either of types $=$, $\geq$ or $\leq$. Can we have constraints that are purely $>$ or $<$ types? If so, how do we convert it into ...
0
votes
0answers
10 views

implementation of coppersmith matrix multiplocation

Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
0
votes
1answer
83 views

LP: multiple optimal solutions, unbounded, infeasible? [closed]

I'd like to ask the following question(s), to help me de-confuse things: $5y + x \geq 7$ $-3y + 4x \geq 5$ $4y - x \leq 15$ $y - 3x \geq -21$ $y - 4x \leq 42$ Given these constraints, what could ...
2
votes
3answers
1k views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
3
votes
1answer
54 views

MILP for similarity

I have the following question and I'm not sure how to formulate it as a mixed integer linear programming problem (if possible): I have a set of products i (1..n) where I'm searching a similar product ...
3
votes
0answers
43 views

On the Fundamental theorem of Linear Programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
0
votes
0answers
21 views

Maximize a variable bounded by a convex hull

Consider the optimization problem: $$\max \theta$$ $$\text{s.t. }\theta\leq min\{A\alpha\}$$ $$\sum_{i=1}^{k} \alpha_i =1$$ $$\alpha_i\geq 0 \text{ for }\forall i$$ where $\alpha=[\...
0
votes
1answer
17 views

Sensitivity Analysis. Does changing the coefficient in the objective function produce a different objective value?

Say the change in the coefficient is within the allowable increase or decrease. Can the objective value change? I'm reading that it doesn't change. But, say the simplex solves the problem and one of ...
0
votes
0answers
8 views

Maximizing throughput through correct ratios

I recently came across this interesting game where I have combined several different types of base stations together to produce a certain amount of energy. However, I believe there is a way of ...
1
vote
1answer
66 views

How to reformulate this model in standard form?

How to reformulate the following linear programming model into an equivalent model that is a linear program in standard form?: Maximize $-e^T |x|$ subject to $Ax \geq b$ x unrestricted where e = (1, ...
1
vote
0answers
51 views

How to derive the Standard Dual using the definition embedded in the Von Neuman Primal and Dual?

Given von Neumann primal Maximize: $c^Tx$ s.t.: Ax $\leq$ b x $\geq$ 0 And von Neumann dual Minimize: $b^T y$ s.t.: $A^T$ y $\geq$ c y $\geq$ 0 How to derive the Standard dual from the Standard ...
2
votes
0answers
43 views

$P:=\{x\in\mathbb{R}^n:Ax\ge b\}, S:=\{c^Tx:x\in P\}$, prove that $S$ is a convex set

Consider the LPP of optimizing the objective function $c^Tx$ over the polyhedron $$P=\{x\in\mathbb{R}^n:Ax\ge b\}$$ Show that the set $$S=\{c^Tx:x\in P\}$$ of values of the objective function over all ...
0
votes
0answers
37 views

Maximizing a sum of minimums → maximizing a single minimum

Let $\Delta_n$ be the standard simplex. Does there exist a function $$f : \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n} \rightarrow \mathbb{R}^{m \times n}$$ such that $$\operatorname*{...
0
votes
0answers
36 views

How to reformulate this optimization problem as a linear program?

Let $Ax \leq b$, $x \geq 0$ define the feasible region. Each constraint defines a hyperplane in $R^n$ and the distance from a point $\hat x$ to a hyperplane is $d_i(\hat x)$ = $(b_i - A_{i,*} \hat ...
0
votes
1answer
38 views

Converting minimizing wasted string when partitioning 200cm into 90,70 and 50cm to Linear Programming problem

Say you have 3 products that require x amount of string to make: Product A: requires 90 cm of string Product B: requires 70 cm of string Product C: requires 50 cm of string String comes to you from ...
1
vote
1answer
271 views

Linear programming alternate optimum solutions

**Q- The Optimum of a linear programming problem occurs at $(1,2,3)$ and $(-1,0,7)$ then the optimum also occurs at? $a)(2,4,6)$ $b)(0,3,5)$ $c)(0,1,5)$ $d)(3,2,1)$ $e)$ None of the above. When ...
2
votes
1answer
1k views

Plotting multiple planes with three variables in 3D using MATLAB

I couldn't figure out, how I could plot three different equations with three variables, namely x,y and z in MATLAB or any other Mathematical Softwares. I know that there's a way we could plot multiple ...
0
votes
1answer
68 views

The fundamental theorem of linear programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
1
vote
1answer
36 views

Expressing a norm as an LP

Let $\mathbf{x}\in \mathbb{R}^n$, and let $\|\mathbf{x}\|_L$ be the sum of the $L$ largest absolute components of $\mathbf{x}$. That is to say, write the (absolute values of) components of $\mathbf{x}$...
0
votes
0answers
28 views

Prove that any hyperplane and halfspace in $\mathbb{R}^n$ is a convex set

$a)$ Prove that a hyperplane in $\mathbb{R}^n$ is convex. Recall that a hyperplane is a set of the form $\{x\in\mathbb{R}:a^Tx= b\}$ for some vector $a$ and scalar $b$. $b)$ Prove that a ...
1
vote
0answers
18 views

Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed and I need help defining some of the variables. To keep the information confidential, I will ...
1
vote
1answer
1k views

Help with Min Ratio Test in Phase II

How can you prove that the min ratio test in phase II in the simplex algorithm ensures that a feasible tableau remains feasible on pivot in linear programming?
0
votes
1answer
46 views

Standard Form of linear programming

How can we prove that all linear programming problem cannot be converted to the form below: \begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& A x = b \\ \end{array} I think we ...
0
votes
0answers
14 views

Wording for programming equation system- Get all possible results for combinations

I stumbled upon a real life example regarding possible combinations for different sets of items (food groups for diets) that then would be programmed to generate an automatic lists of recipes based on ...
0
votes
1answer
61 views

Linear Program with Mutually Exclusive Variables - Best Method to Solve

So I'm pretty sure that its not possible to set up a linear-program that has non-binary mutually exclusive variables (but would love to be wrong here). It seems like it would be possible to solve the ...
0
votes
0answers
7 views

Prove if $x,y$ are vectors and $A$ is a matrix then $\exists x$ st $x \le 0$ and $Ax \le b$ xor $\exists y$ st $A^Ty\ge 0, y\ge 0$ and $by<0$

I'm supposed to use the fundamental theorem of LP, weak duality and strong duality to prove this. Fundamental Theorem of LP: 1) If there's a feasible solution there's a basic feasible solution 2) ...
0
votes
1answer
59 views

Minimization problem with absolute value in objective function

Consider the following (piecewise linear) minimization problem where $(x,y) \in \mathbb{R}^2$. $$\begin{array}{ll} \text{minimize} & |x| + y\\ \text{subject to} & x + y = 2\\ & x \le ...
0
votes
1answer
101 views

Converting Standard form to Canonical form

This is what my lecturer says on standard and canonical forms: "Two particular forms of the linear programming problem are of interest for m equations in n unknowns. These are called the standard form,...
1
vote
1answer
73 views

Write LPP in canonical form

A health food store packages a nut sampler consisting of walnuts, pecans, and almonds. Suppose that each ounce of walnuts contains $\color{red}{\text{$12$ units of protein}}$ and $\color{blue}{\text{$...
2
votes
0answers
62 views

What's the difference between GLPP and LPP

$a)$ Express the following optimization problem as a linear programming problem(LPP): $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$ Hint: you will need to express the ...
1
vote
0answers
19 views

Assigning range of values to unknowns in an inequation

I am trying to calculate weights to use for a program that is using a minimax tree to search the best possible move for a board game. I have a bunch of inequations that need to evaluate to true, ...