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

learn more… | top users | synonyms

3
votes
4answers
59 views

Feasible point of a system of linear inequalities

Let $P$ denote $(x,y,z)\in \mathbb R^3$, which satisfies the inequalities: $$-2x+y+z\leq 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
1
vote
1answer
21 views

Show identity using Cauchy-Schwarz' inequality

For $v=(v_1,...,v_n)^T \in \mathbb R^n$ we let $f(v)=|v|^2=v^Tv=v_1^2+...+v_n^2$. Show using Cauchy-Schwarz' inequality: $u^Tv \leq|u||v|$ that, $$ 0 \leq (1-\lambda )f(u)+\lambda f(v)-(f((1-\lambda )...
-4
votes
0answers
27 views

Tuition service for math CBSE [on hold]

Can anyone suggest best tuition service for CBSE 12th grade math in Kuwait?
1
vote
0answers
12 views

Two phase method in linear programming

suppose following tableau came after one iterations in first phase of a two phase method problem, here $s_1$ is a surplus variable and $s_2$ is a slack variable $w$ is a artificial variable. i tried ...
0
votes
1answer
10 views

Formulating a problem involving sets with ILP

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost ...
1
vote
0answers
11 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
5
votes
1answer
4k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ x_1&&&-&x_3&...
2
votes
1answer
634 views

Binary constraint integer programming problem

I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let $x$ and $y$ be integer variables bounded at 1000. How can you ...
0
votes
0answers
18 views

Combination of certain linear-programming topics new?

I am writing a book on Linear Optimization. Its goal is to present material in a particular form which has not been encountered yet in the literature to the best of my knowledge. I am aiming at the ...
0
votes
0answers
26 views

Linearise product of two non-negative variables

Is there a trick to linearise the product of two non-negative (decision) variables in linear optimisation? Let $x_1$ and $x_2$ be these variables with $0 \leq x_1 \leq a$, $a \in \mathbb{R}_+$ and $...
0
votes
1answer
22 views

maximize 3-variable linear function [version 2.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}\frac{x_2}{6}...
0
votes
1answer
36 views

maximize 3-variable linear function [version 1.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}x_2 + \frac{...
0
votes
1answer
64 views

McCormick Envelopes with more then 2 variables

I'm trying to solve a bilinear optimization problem by linearizing the problem using the McCormick Envelope method. It's quite a simple method when you are only using the product of two variables, ...
2
votes
3answers
2k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
0
votes
0answers
25 views

Maximum length of a ray shot from an interior point of a polytope?

assume that I have a polytope $\bf{Ax \le b}$ and I also have an interior point corresponding to the nominal values of x, namely $\bf{x^0}$. Given a weight w for each dimension (coming from uniform ...
1
vote
1answer
394 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
1answer
558 views
6
votes
1answer
591 views

Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
1
vote
1answer
322 views

What happens if we remove the non-negativity constraints in a linear programming problem?

As we know, a standard way to represent linear programs is $$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ with the associated dual ...
1
vote
2answers
932 views

Removing linear redundant constraints using Gauss 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 ...
2
votes
2answers
568 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? $\...
1
vote
2answers
39 views

How to Solve a linear matrix equation of an array $M = BMC$ where $ B$ and $C$ are known

Adding to the question's description : I am doing Feature extraction from videos and i am trying to implement this one line of mathematical equation to matlab or even any algorithm . let's say I ...
0
votes
1answer
22 views

Contradictory system of linear inequalities

Assume that $(F_i)_i$ is a system of linear inequalities in $n$ variables, of the form $F_i(x_1,\ldots, x_n) > 0$, where $F_i(x_1, \ldots, x_n) = a_{i,1}x_1 + a_{i,2} x_2 +\ldots + a_{i,n} x_n + ...
6
votes
4answers
978 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and $b$...
1
vote
0answers
11 views

Why does the Dantzig cut require the constraint data to be integral?

Given the following integer linear program, (ILP) $\min c'x$ subject to $Ax \ge b, x \in \mathbb{N}_0$ where all elements of $A$ and $b$ are integral, and assuming its linear-program relaxation (...
1
vote
0answers
24 views

IF statement as Linear Constraint

I am writing a linear program, but I am currently having troubles writing a certain constraint, which is basically an IF-statment. I will try to explain it as detailed as possible: IF: $x_{it'}(t' +...
0
votes
0answers
21 views

Solving Equations involving max operation

I would like to know how to solve this set of equations for v*(h) and also v*(l) Assume all other variables are known..concentrate on the 3rd equality in case of v*(h)..the first 2 are not needed. I ...
2
votes
1answer
76 views

Linear program with two equality constraints

Compute the minimal value of $$x_1 + 2x_2 + 3x_3$$ when $x_1$, $x_2$, $x_3$ satisfy $$x_1 − 2x_2 + x_3 = 4$$ $$−x_1 + 3x_2 = 5$$ and $$x_1 \ge 0, \qquad x_2 \ge 0, \qquad ...
0
votes
0answers
32 views

Minimizing a function including max functions

Consider the following problem. Let $\mathcal{N} = \{1,2,\ldots,N\}$ and $\mathcal{N}^i = \mathcal{N}\setminus \{i\} $. For each $i \in \mathcal{N}$ and for each $S \subset \mathcal{N}^i$, we have a ...
0
votes
0answers
19 views

modelling a composite objective function (max + argmax) as an (integer) linear program

Suppose $\mathbf{x} = [x_1, x_2, \ldots, x_n]$, where $x_i \in \{0, 1\}$ are binary variables. We know for a fixed $\mathbf{w}$ the following problem is an Integer Linear Program: $$ \arg\max_{\...
0
votes
0answers
41 views

Fourier-Motzkin elimination number of constraints

I have this question: Consider Fourier-Motzkin elimination algorithm. Let n = 2^p+p+2, where p is non-negative integer. Consider a polyhedron in R^n defined by the m = 8(n 3) constraints. +-xi+-xj+-...
0
votes
1answer
402 views

Linear programming: Maximize minimum of linear functions

For a project I need something solved, it screams linear programming. If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
-1
votes
0answers
13 views

reference request quadratic optimization problem

I have this problem and it seems similar to something people must have studied in quadratic optimization/non-convex optimization. $\min_{a,b \in [0,1]^n} a^TM b\\ \text{subject to. } a^TQb\geq \alpha$...
0
votes
0answers
29 views

min cost flow: getting primal solution from dual

Let $(N,A)$ be directed acyclic graph with arc weights $w: A\rightarrow \mathbb{N}$. I want to solve the following LP: $$ \text{min} \sum _{(i,j)\in A} x(j) - x(i) $$ subject to $x(j) - x(i) \geq w(a)...
2
votes
1answer
33 views

converting $\max\{\ldots,\ldots\}$ function to a set of $\min\{\ldots,\ldots\}$ functions

Suppose $\max\{A,B\} = A$ if $A\geq B$ and $\max\{A,B\} = B$ if $A <B$. Similarly, $\min\{\}$ is defined. We know that $\max\{A,B\} - A - B= - \min\{A,B\}$. Is it possible to write $\max\{A,B,C\} ...
0
votes
2answers
46 views

Coefficients($\sum 1$) of equation to get maximum output

Lets say we have $4$ variables: $$ x_1, x_2, x_3, x_4 $$ with coefficients: $a,b,c,d$ respectively, and output $y$ With different combinations of $a,b,c,d$, we have a blackbox/unknown function, that ...
1
vote
0answers
41 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
0
votes
0answers
21 views

Formulating a linear transportation problem as a stochastic linear program

[Question provided in picture]http://i.imgur.com/avoARFG.jpg[/img] I am having trouble with part b of this question. For part a, I have the following: let xij = number of units produced by plant i ...
2
votes
1answer
43 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
0
votes
1answer
26 views

Formulating deterministic and stochastic production models (not solving them) [Beginner's Operations Class]

Question provided in picture This question has been troubling me as I am not used to questions without numbers as it is hard for me to visualise. I also find stochastic problems hard in general. &...
3
votes
1answer
3k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ (...
0
votes
2answers
25 views

Formulating an optimisation problem into a mixed-integer problem

I'm not sure if I understand this question and was wondering if anyone could provide any insight to an answer. The only thing I can think of adding is a constraint: "x2 = integer", so I'm clearly ...
0
votes
0answers
20 views

How to linearize a double sum of product of binary variables?

I have a double summation of the form $$ x_{kn}\sum_{k'\in K}\sum_{n'\in N} x_{k'n'} A_{k'n}\leq B_{kn},\quad\forall\; k\in K,n\in N $$ where $x_{kn}$ is a binary variable. How to linearize this ...
0
votes
1answer
25 views

When modeling a multi-objective problem, is there a simple way of choosing to fully minimize one function, then to go on and minimize the second?

I am modelling a problem where I have two objectives. My goal is to fully minimize the first objective function, then choose among the solutions that fully minimized the first objective function to ...
1
vote
2answers
29 views

LP: add extra costs in the objective function for every variable which is not equal to $0$

I am trying to optimise an LP problem but extra costs should be added if a variable is larger than $0$. For example, if we have the following objective function: $$\text{minimize} \qquad 2X_1 + 3X_2 ...
0
votes
0answers
11 views

Ray between vertex and point inside a polytope

Let $P$ be a polytope, let $v \in P$ be a vertex of $P$, and let $x \in P$ such that $x$ is not a vertex. Consider the ray $$\forall t>0, \phi(t)=v+t(x-v).$$ Let $t_0$ be the maximal $t$ such that ...
1
vote
1answer
43 views

Show that exactly one of the following two systems has a solution.

Let A be a $m \times n$ matrix, $\mathbf{c}$ an $n$-dimensional ector and $\mathbf{b} \ge \mathbf{0}$ an $m$-dimensional vector. Show that exactly one of the following two systems has a solution: $\...
0
votes
0answers
14 views

Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
0
votes
0answers
8 views

Reduced cost in linear programming maximization sensitivity analysis?

My sensitivity report of maximization problem shows negative reduced cost although my optimal values of variables are not zero. So, what does it mean by the negative values of reduced cost? Here is ...