Questions on linear programming, the optimization of a linear function subject to linear constraints.
0
votes
1answer
98 views
Linear programming / linear optimization with R? [closed]
Any good books or websites that teach linear programming / linear optimization with R? Thanks.
Edit (Jan 6, 2013): The following R code is an example by using the "lpSolve" package.
...
-1
votes
1answer
77 views
Finding an $O(n \log n)$ time algorithm for an optimization problem
Consider the following optimization problem:
Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
28 views
using the ellipsoid algorithm to find a poly time algorithm for the optimization problem
Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in
$\mathbb{R}^n.$ Find
$\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
2
votes
1answer
256 views
Linear programming / linear optimization video lectures?
Is there a good set of linear programming / linear optimization video lectures somewhere?
I found "Linear programming and Extensions" by Prof. Prabha Sharma, Department of Mathematics and ...
0
votes
2answers
517 views
Linear Programming Problem Using the Two-Phase Method
I have been given the following LP problem and asked to use the two phase simplex method to solve it.
I believe there isn't a solution, but would anyone be able to confirm this for me? Thanks.
max
...
1
vote
0answers
140 views
Linear programming: basic solutions?
http://www.math.toronto.edu/kergin/236_t1_2.pdf
For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
-5
votes
1answer
94 views
What approach can be used to solve this? [closed]
The problem can be found here.
The game is simple. You initially have ‘H’ amount of health and ‘A’ amount of armor. At any instant you can live in any of the three places - fire, water and air. ...
0
votes
0answers
15 views
Optimization | Groups with limited spots and priority
As someone at math.stackexchange helped me with this solution, its still not quite right
Problem:
list $L$ can hold $m$ items.
$p_i$ is percent of items from the group than go in $L$ (for i = ...
2
votes
0answers
147 views
Reconstructing an optimal Simplex tableau from an optimal solution
I have here a bounded LP with infinite optimal solutions:
...
2
votes
1answer
322 views
What does basic solution mean?
Linear programming: basic solution?
If the matrix consists of
$$\begin{bmatrix}1&-2&0&0&0\\-3&6&1&3&0\\0&0&2&6&-1\end{bmatrix},$$
how is it that there ...
0
votes
1answer
53 views
Inequalities with matrices
For a linear system of equations constrained by inequalities, is $ Ax \le b => y^TAx \le y^Tb $ acceptable? Or does that not generally hold.
($ y^T $ being the transpose of $y$).
2
votes
0answers
112 views
intuitive explanation of Primal-Dual algorithms
I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
1
vote
2answers
47 views
What's the relation between the non-convex sets and the hardness of ILP problems?
If some or all of the unknown variables are required to be integers,
then the problem is called an integer programming (IP) or integer
linear programming (ILP) problem.
If understand ...
1
vote
1answer
437 views
A question about the operation research and simplex method
For the simplex method, we need to add slack variables. My question is how to determine how many slack variables should be considered in the LP problem? I don't quite get why in the cases to find out ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
0
votes
0answers
24 views
Lagrangian duality: revised
Consider the following LP:
$\max$ $\sum_{i=1}^N b_i \pi_i$
s.t. $\;\;$ $\pi_i-\pi_j\leq 1 $ $\quad$ for each $(i,j) \in \tilde{A}$
$\sum_{i=1}^N a_s^i \pi_i \leq 1$ for each $s \in S$
This ...
0
votes
0answers
174 views
Simplex Tableaux Problem
I have the following LP which I need to solve using the simplex method. I know there are no feasible solutions as there are constricting constraints. How do I use the Tableaux method to show this?
...
1
vote
1answer
50 views
Simple LP - simplex problem
I have a LP with constricting constraints, i.e. there is no feasible region. How would I use the simplex method to show this?
After one iteration of the simplex method I have found no negative values ...
0
votes
2answers
80 views
When does $\max x+y $ subject to $ax+by \le 1$, $x,y\ge 0$ have a unique optimal solution?
From reading online I found someone said that it has a unique optimal solution when $a$ and $b$ are positive and $a \neq b$.
Could someone explain why this is the case?
I know that if $a = b$ then ...
1
vote
1answer
350 views
Example of a quadratic programming problem with no optimal solution on vertices?
Is there a way to write a quadratic programming problem with
two variables
bounded, nonempty feasible region
linear constraints
and yet have none of the vertices of the region optimize the ...
2
votes
1answer
189 views
Developing Constraints for a linear programming based problem
Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule.
That said, I have a few questions regarding the process. I haven't ...
0
votes
1answer
17 views
why the optimized point always appear in the interception in LP problem
As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.
3
votes
0answers
41 views
relation between solution of a linear program and its perturbation
I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:
$$
\max_j c' x_j
$$
Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
0
votes
1answer
69 views
Parametric Linear Program: Continuous Solution?
Consider the parametric linear problem
$$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$
$$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$
where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
1
vote
1answer
46 views
Proof required for an alternate method in solving a linear programming problem
Suppose that P and Q are two of the corner points of the feasible region lying completely in the first quadrant. In addition, P is located at SE of Q*.
z = 0 (or more specifically, Ax + By = 0) is a ...
0
votes
0answers
75 views
Basic optimisation problem ( dual problem of the Linear Programming problem)
Find the dual problem of the following Linear Programming problem
$$ \min z = c_1x_1 + c_2x_2 + \dots + c_nx_n,$$
subject to:
\begin{array}{c}
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1\\
...
0
votes
0answers
95 views
Is it possible to linearize the non-linear equation in this linear programming?
Have typed the question is latex format, here it is:
1
vote
0answers
13 views
Use Exact Non-linear formulation or a linear approximation?
I am writing a paper that discusses results to solve stochastic problems with recourse analytically. The problem is nonlinear. I can also write an approximate stochastic linear program to sove the ...
3
votes
1answer
96 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
0answers
98 views
linear programming
Suppose you have won \$ 6000 from OK Grand challenge promotion and you want to invest is. Upon hearing the news , your two differnt friends Mukanya and Mhofu offer you each an opportunity to become a ...
0
votes
1answer
45 views
Can standard Linear Programming algorithms return all valid solutions without losing their efficiency?
I have a (generalized) Linear Programming problem to solve. I anticipate exactly two equally valid optimizations of my objective function. I would be happy if I could receive both these points; it ...
0
votes
2answers
194 views
Need Homework Help: A small corportion borrowed $500,000, some at 9%, 10% and 12%. Use a system of equations--how much was borrowed at each rate if…
A small software corporation borrowed 500,000 cash to expand its software line. The corporation borrowed some of the money at 9%, some at 10%, and some at 12%. Use a system of equations to determine ...
0
votes
1answer
94 views
Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and..
Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and an optimal solution $(\bar{x},\bar{z})$ of the problem 2 $\min z $ s.t $z\ge f(x)\,, x\in \mathbb{R}^n$ ...
2
votes
1answer
68 views
Maximizing a linear combination of certain integers
Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
1
vote
2answers
154 views
Find a nonnegative basis of a matrix nullspace / kernel
I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$).
This problem comes ...
0
votes
1answer
131 views
LP: nonbasic solution made into basic solution, help me with this terminology
Related chat here, reading the Bertsimas book now on pages 50-51. By the way, I am gathering Linear-Programming -related studying material here, welcome to read a book and have coffee :)
I cannot ...
1
vote
0answers
45 views
Linear Optimization Problem - Assign Objects to People
Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values ...
2
votes
1answer
110 views
How relevant is mathematical optimization today?
That's it. That's all I'd love to know from you guys. Mathematical optimization, with the aid of today's software. Do you think it's still relevant in today's world?
0
votes
2answers
90 views
Reduced cost zero for the two-phase Simplex?
I cannot understand the line -12, -4, -5, 1, 1, -1, 0, 0, 0. Now the formula $\bf c - \bf A ^t \bf y$ when $c=0$ will result into the line. It is just many times a ...
1
vote
2answers
296 views
Optimality conditions and Directions in Simplex method
I am trying to understand the optimality conditions in Simplex -method, more in the chat here -- more precisely the terms such as "reduced cost" i.e. $\bar{c}_j=c_j-\bf{c}'_B \bf{B}^{-1} \bf{A}_j$ and ...
1
vote
1answer
51 views
Interactive Vizualizer of different Simplex -methods?
My book [1] around the pages 80-100 outlines the theories behind different simplex methods such as Naive-Simplex, Revised-SImplex, Full-tableau-Simplex, Dual Simplex, etc-simplex --. It is very dry ...
1
vote
0answers
37 views
Using duality to establish a relationship between in two-stage linear programming
I'm currently working on a problem that involves a two-stage linear program (LP). For simplicity, I refer to the LP in first stage as LP$_1$, and the LP in the second stage as LP$_2$. The relationship ...
1
vote
3answers
142 views
Integer combination
i want write a module to find the integer combination for a multi variable fomula. For example
$8x + 9y \le 124$
The module will return all possible positive integer for $x$ and $y$.Eg. $x=2$, ...
0
votes
1answer
84 views
Solving an optimization problem involving reciprocals
I am trying to solve the following minimization problem, perhaps by getting it into a LP form:
Let $u= [u_1, u_2, ...u_N]^T$ a column vector, and $v=[{1\over u_1}, {1 \over u_2}, ...{1 \over u_N}]^T$ ...
0
votes
1answer
229 views
Using max/min operators in linear programming.
I'm currently implementing a Markov Decision Process using the solver GLPK, I'm following the lecture by Vincent Conitzer, and there is a step I don't understand between the theoretical problem and ...
2
votes
1answer
111 views
Books on AI, programming, optimization
I'm studying math (just started) and I like programming as well (just started this too), is there a career or a branch of research including deep aspect of this two aspects? Is there someone among you ...
0
votes
0answers
41 views
Object selection algorithm to fulfill multiple value criteria
Sorry if I don't explain this too well, but here goes:
I'm trying to find an algorithm that will randomly select objects with different attributes to match specific criteria. The best way to explain ...
1
vote
1answer
171 views
Optimization with non-negativity and norm constraint
I am facing the following optimization problem:
$$\min_x w^tx \\
s.t. ||x|| = 1, \forall i: x_i \geq 0
$$
where $w$ and $x$ are real valued vectors. How would I solve this?
My background is not ...
14
votes
1answer
115 views
How low can the approval rating of a majority candidate be?
“Ostrogorski's paradox” describes a strange situation in which voters decide on candidates based on issues in platforms, but on each issue of the platform, the majority of voters disapprove of the ...
1
vote
0answers
19 views
Background of choosing standard for of a linear program as type III inequalities?
In linear programming where we seek to minimize $c^Tx \to \text{min}_{x\in P}!$
with respect to some inequality constraints,
why do we choose $P$ in the form
$Ax \leq b$, $x \geq 0$
as the ...
