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

learn more… | top users | synonyms

5
votes
0answers
665 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} f(x)p(x)...
11
votes
6answers
8k views

Linear Programming Books

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
5
votes
1answer
773 views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
4
votes
5answers
6k views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
12
votes
3answers
289 views

Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
0
votes
1answer
758 views

Reduced cost vector in the phase I of the Two-phase simplex?

I am trying to understand the part in red. The left is the standard form problem and the right is the auxiliary problem. Now I can understand until the red i.e. $\bar c =(-1,-1,-3,-1,-2,0,0,0)$. The $...
3
votes
1answer
891 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \...
1
vote
1answer
918 views

travelling salesman understanding constraints

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
7
votes
2answers
10k views

Primal and dual solution to linear programming

Lets say we are given a primal linear programming problem: $\begin{array}{ccc} \text{minimize } & c^{T}x & &\\ \text{subject to: } & Ax & \ge & b \\ & x & \ge & ...
6
votes
3answers
5k views

Primal- degenerate optimal, Dual - unique optimal

Simple question- Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
2
votes
2answers
505 views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
1
vote
2answers
1k views

$\ell_0$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min:\|x\|_0$ subject to:$Ax=b$. $\|x\|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has ...
2
votes
1answer
296 views

Linear Programming 3 decision variables (past exam paper question)

This is an exam question I was practising. I have the general understanding of Linear programming, but how would you go about finding the Decision Variables, Objective function and Constraints for ...
2
votes
0answers
188 views

Linear optimization problem.

I have copied the entire problem from the book. It has 7 parts. Please show me how to do any 1-2 of the parts. I mostly understand the problem, but need to see a fully woked out problem. Given a $m$ ...
2
votes
3answers
1k views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
12
votes
3answers
16k views

Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
5
votes
5answers
14k views

Converting absolute value program into linear program

I have the generic optimization problem: $$ \max c^T|x|$$ $$ \text{s.t. } Ax \le b $$ $x$ is unrestricted How do I convert it into a linear programming problem? Online I read something about ...
11
votes
2answers
8k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value (...
7
votes
1answer
9k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
5
votes
1answer
679 views

How does multiplying a primal constraint by a constant change the dual solution?

Suppose we have the problem $\min c^T x$, subject to $Ax=b, x \geq 0$. Suppose that this program and its dual are feasible. Let $\lambda$ be the optimal solution of the dual. If the $k$th constraint ...
4
votes
0answers
78 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
1
vote
2answers
852 views

Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

So, there are four inequalities: $$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$ If we draw all those ...
0
votes
1answer
97 views

Which optimization class does the following problem falls into (LP, MIP, CP..) and which solver to use

I have the following optimization problem. I want to solve it using a computer solver. But I am not sure which problem class it falls into or which solver to use. Problem: There is a set of objects ...
5
votes
2answers
227 views

Convert a piecewise linear non-convex function into a linear optimisation problem.

Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different. Convert $$\min z = f(x)$$ where $$f(x) = \left\{\begin{matrix} 1-x, &...
4
votes
1answer
2k views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
3
votes
2answers
2k views

Simplex method : Duality by Bazaraa

I use great textbook (Linear Programming and Network Flows by Bazaraa II ed) On the page 240 the author states that for every primal problem, regardless of it's type (canonical or standard), dual ...
3
votes
1answer
332 views

Pivoting and Simplex Algorithm

I would like to understand exactly how the pivoting works geometrically in Simplex algorithm. What is meant geometrically by moving a vector into BFS and moving out one. Also, what is the geometrical ...
3
votes
1answer
2k views

Strict inequalities in LP

How should we deal with strict inequalities in a linear programming problem? For example: inequalities such as $ax< b$;
0
votes
1answer
2k views

Example about the Reduced cost in the Big-M method?

I want to gather examples about the reduced cost in different cases, now for the Big-M method. I hope this makes the methods more accesible. So How does the Big-M method work with the below? $...
5
votes
1answer
657 views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} &...
5
votes
2answers
659 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
4
votes
1answer
133 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
4
votes
3answers
2k views

Linear programming problem formulation

Stuck in this problem for quite a while. Anyone can offer some help? The problem is as follows: Fred has $5000 to invest over the next five years. At the beginning of each year he can invest money in ...
2
votes
2answers
3k views

Nash Equilibrium for the prisoners dilemma when using mixed strategies

Consider the following game matrix $$ \begin{array}{l|c|c} & \textbf{S} & \textbf{G} \\ \hline \textbf{S} & (-2,-2) & (-6, -1) \\ \hline \textbf{G} & (-1,-6) &...
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 ...
2
votes
1answer
57 views

How does one use the 'input/hr' column in the table below in setting up the problem?

I have to set up a linear programming problem corresponding to the following scenario: If my understanding of the problem is correct, I use $mod$: Let $i$ be $A$ or $B$. Let $x$ be amount ...
2
votes
1answer
562 views

Reconstructing an optimal Simplex tableau from an optimal solution

I have here a bounded LP with infinite optimal solutions: ...
2
votes
1answer
84 views

What needs to be linear for the problem to be considered linear?

Harry Altman presented an excellent question in a comment here: What needs to be linear for the problem to be considered linear? So is it enough to a have linear objective function or other ...
2
votes
2answers
378 views

How to calculate volume given by inequalities?

I need to find the volume of the 3d space that is given by the following conditions: \begin{array}{c} 0 < x_1 < 1\\ 0 < x_2 < 1\\ 0 < x_3 < 1\\ x_1 + x_2 + x_3 < a. \end{array}...
1
vote
0answers
95 views

Warm start of simplex algorithm after update of constraint matrix

Assume we found an optimal solution $\mathbf{x}_1$ of the linear program \begin{gather} \max \mathbf{n}^T\mathbf{x}\mbox{ s.t. }A\mathbf{x} \leq \mathbf{b}\tag{1} \end{gather} using the simplex ...
1
vote
1answer
860 views

Reduced cost in the Phase II of the two-phase Simplex?

My lecture slides outline how the two-phase simplex works: this table shows the end result of the phase I for the standard-form problem and the auxliary table of the phase I here. I understood until ...
1
vote
3answers
200 views

Is an unit-cube polyhedron? What about other platonic solids?

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in \...
1
vote
1answer
2k views

How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

I have this linear program $$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 \end{...
1
vote
2answers
330 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\\...
1
vote
1answer
70 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + \...
0
votes
1answer
50 views

Travelling salesman problem as an integer linear program

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear ...
0
votes
1answer
70 views

Express the constraint “$x = 0$ or $y = 0$” in linear programming

How to express the constraint "$x = 0$ or $y = 0$" in a linear program? Is it possible at all?
0
votes
1answer
74 views

LP problem involving producing assemblies

I have to construct an LP problem based on the ff scenario that might be similar to a scenario in another question (in the sense that I felt the need to use $mod$): The productivities are ...
0
votes
0answers
120 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
4
votes
5answers
101 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 ...