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

learn more… | top users | synonyms

1
vote
1answer
32 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 )...
1
vote
0answers
14 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 ...
3
votes
4answers
70 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 ...
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
12 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 ...
0
votes
0answers
27 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
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
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
37 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
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 ...
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 + ...
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 ...
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
20 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_{\...
-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\} ...
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 ...
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 ...
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. &...
2
votes
1answer
44 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
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 ...
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
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 ...
1
vote
1answer
44 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 ...
1
vote
1answer
33 views

Conditions for uniqueness of solution to a linear system of equation

Consider a $n\times n$ M-Matrix $\mathbf{A}$ and a $n\times n$ non-negative and non-zero matrix $\mathbf{B}$. Also, let $\mathbf{x}$ and $\mathbf{b}$ be two (non-zero) n-column vectors. I am looking ...
2
votes
1answer
62 views

Minimize absolute difference of two integers

I have 4 known positive variables - $p$, $q$, $r$ and $s$ and two unknown positive variables $x$ and $y$. How can I choose $x$ and $y$ such that absolute difference of $(p+x \cdot r)$ and $(q+y \cdot ...
0
votes
0answers
33 views

Solution of diophantine equation with lowest c

Lets say I have a diophantine equation , aX - bY = c Now, for some (a,b,c) I may not have any integer solution at all. But lets say , I write the equation in this way , aX - bY = c + p p is an ...
1
vote
1answer
26 views

How to minimize a linear function over a halfspace efficiently and intuitively

Consider the following fundamental problem: Two methods: By duality: ($\lambda, b \in R$) $L(x,\lambda)=c^Tx+\lambda(a^Tx-b)=x^T(c+\lambda a)-\lambda b \ \ $. Therefore, $g(\lambda)=-\...
0
votes
1answer
20 views

LP problem: Giving variables the same value or 0

If I have the following objective function: $$\min X_1 + X_2 + X_3 + X_4$$ How could I ensure that the variables $X_1, X_2, X_3$ and $X_4$ either have the value of 0 or they could have a random ...
4
votes
0answers
64 views

I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
0
votes
1answer
20 views

GLPK/Linear Programming - if conditions

Imagine that I have two variables fw (>= 0) and a (binary) and my objective function is to minimize: fw. In the constraints part, I want to ensure (among other ...
0
votes
1answer
37 views

Minimize linear function with $\ell_1$ norm regularization and positive semidefinite constraint

I am running into the problem like this: $\underset{\mathbf{X}\succ0}{\text{minimize }} vec(\mathbf{A})^{\top}vec(\mathbf{X}) + \lambda ||\mathbf{X}||_1$ I am think about maybe one can minimize a ...
0
votes
0answers
13 views

Solving Binary Linear Programming Problem Using KKT

Execuse me, I know that if I searched a lot I could find the answer, However I have already did my research and I am running out of time. I need the detailed solution of the following linear problem (...
1
vote
3answers
45 views

Easier way of finding out whether a given linear programming problem has optimal solution or not

I have the linear program $$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$ I can solve it using Simplex algorithm, but I ...
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 ...
1
vote
0answers
5 views

Complementary Facets of Pointed Cone

I am looking at a particular full-dimensional pointed cone $C \subset R^{11}$ with $14$ generators. In matrix form, with each column being a generator, I have the matrix \begin{pmatrix} 1 & 1 &...
1
vote
1answer
30 views

Dual form of $L_1$ norm approximation as a linear programming problem

According to my text: Given an overdetermined system, the residual vector is: $$\textbf{r} = \textbf{Ca} - \textbf{f}$$ The $L_1$ norm approximation seeks to minimize the residual r: $$\text{...
1
vote
0answers
21 views

How can I show the corresponding dual solution is unique when the given primal solution is nondegenerate, basic feasible?

the given problem is to show that if $x_1,...,x_n$ is a nondegenerate basic feasible solution of the primal LP max $\sum_{j=1}^{n}c_jx_j$ s.t. $\sum_{j=1}^na_{ij}x_j\leq b_i, \forall i\in\{1,...,...
3
votes
3answers
36 views

Maximize system of linear equations

Suppose you have the system $$ \begin{bmatrix} 4 & 3\\ 1 & 7\\ 5 & 9\\ 2 & 4\\ \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix} $$ How ...
0
votes
0answers
16 views

AMPL - Step by Step mode

Is there a way to solve a problem using AMPL in a step by step(or a verbose, or a debug) mode? Preferably showing all basis exchanges? The manuals of AMPL make reference to script development, but i ...