Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
493 views

MATLAB LP formulation of investment problem (in Bertsimas' lecture notes)

I wish to write MATLAB codes to solve the following linear programming problem found in Bertsimas' lecture notes: My attempt was as follows (sequence of variables for f' is A, B, C, D, E, Cash1, ...
0
votes
1answer
58 views

intuitive explanation of sparsity / references

I know it is a vague question, but I am confused by why/when we actually want sparsity of a matrix. For example, interior-point methods work better when constraint matrix is sparse. Similarly, it is ...
1
vote
1answer
943 views

Linear combination question in Linear Programming Problem

I have two constraints in a linear programming model: x1 + x2 <= 5 x1 >= 2 Note that there are no nonnegativity constraints so the problem is unbounded from below. The point (2,3) is the only ...
1
vote
2answers
444 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq \begin{pmatrix}0\\...
0
votes
1answer
76 views

Solving equation of the form $Axb^Tx = y$

I have a square, invertible $n\times n$ matrix $A$, and column vectors $b$ and $y$. I'd like to find a column vector $x$ such that $Axb^Tx=y$. I suspect there's some way to get it into a QP form, but ...
0
votes
1answer
291 views

Are these solutions to a LP problem feasible? basic?

Consider the following LP: \begin{align*} \max 8x_1 + 14x_2 + 12x_3 + 50x_4\\ \text{s. t. } x_1 + 2x_2 + 2x_3 + 16x_4 &\le 8\\ 2x_1 + 3x_2 + 4x_3 + 5x_4 &\le 15\\ 5x_1 + 6x_2 + 8x_3 + 10x_4 &...
-1
votes
1answer
164 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
54 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| =n/...
3
votes
1answer
1k 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 Statistics,...
0
votes
3answers
2k 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
1answer
3k 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 ...
3
votes
1answer
1k views

Reconstructing an optimal Simplex tableau from an optimal solution

I have here a bounded LP with infinite optimal solutions: ...
4
votes
1answer
10k 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
74 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$).
4
votes
0answers
419 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
194 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 correctly, ...
2
votes
1answer
2k 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
1answer
118 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
612 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
1k 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 objective ...
4
votes
1answer
1k 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
23 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
128 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
213 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
113 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 South-East of Q*. z = 0 (or more specifically, Ax + By = ...
1
vote
0answers
22 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 ...
6
votes
1answer
982 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 ...
0
votes
1answer
57 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
3k 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
1k 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
360 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 ...
4
votes
5answers
2k 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
686 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 ...
2
votes
0answers
225 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
191 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
2k 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 ...
2
votes
2answers
3k 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
96 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
101 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 ...
2
votes
3answers
212 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$, $y=12$...
0
votes
1answer
118 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$ ...
3
votes
1answer
2k 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 ...
3
votes
1answer
451 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 ...
2
votes
1answer
1k 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 ...
16
votes
1answer
216 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
28 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 ...
1
vote
0answers
346 views

Question simplex method application criteria?

Can we apply simplex method if one or more equation are equal to zero. tell me full criteria my question example is as follows: Maximize: $z=135x+50y$, subject to: $$\begin{align} 2x+\frac{1}{2}y&...
4
votes
2answers
5k views

LP relaxation for integer linear programming (ILP)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
0answers
129 views

Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
1
vote
0answers
207 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...