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

learn more… | top users | synonyms

5
votes
0answers
637 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} ...
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 ...
9
votes
6answers
7k 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 ...
4
votes
5answers
5k 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 ...
4
votes
1answer
653 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\\ ...
0
votes
1answer
682 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 ...
2
votes
1answer
524 views

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

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
1
vote
1answer
786 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 ...
12
votes
3answers
14k 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 ...
6
votes
1answer
203 views

What is the minimum number of guesses in order to guarantee to win the prize?

Your friend will pick a $4$-letter word and you will make guesses in order to find it. -A word can contain only the letters $A, B, C,\:\text {and} \:D$, and they can be used more than once. ...
7
votes
2answers
9k 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 & ...
5
votes
2answers
2k views

Understanding proof of Farkas Lemma

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying. In the first sentence on p.113: "If (I) holds, then the ...
3
votes
1answer
334 views

Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps. I'm using the example from chapter ...
2
votes
2answers
371 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
2k 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
2answers
910 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 ...
0
votes
1answer
539 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...
0
votes
1answer
72 views

Optimum exists but not extreme point in Standard Form LP problem?

Standard form problem $$\min \bar c^T \bar x \text{ so that } A \bar x=\bar b, \bar x\geq \bar 0$$ I am thinking the point II (Finnish) i.e. optimum exists but it is not extreme point, why it ...
2
votes
1answer
212 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
183 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
1answer
3k views

Simplex Method row operations help?

before programming an algorithm which implements the simplex method, I thought I'd solve an issue before the actual programming work begins. For some reason, I can NEVER get the correct answer. I've ...
0
votes
1answer
670 views

Linear Programming question

I am kind of lost on this problem and would like it if I can get help on this. Matching Pennies. In this simple two player game, the players (call them R and C) each choose an outcome, heads or ...
5
votes
5answers
11k 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 ...
9
votes
2answers
7k 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 ...
8
votes
2answers
3k views

What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
4
votes
0answers
76 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?
7
votes
1answer
8k 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 ...
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 ...
1
vote
2answers
760 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
93 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 ...
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? ...
4
votes
1answer
1k 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 ...
4
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\\ ...
4
votes
2answers
578 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 ...
3
votes
1answer
319 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 ...
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
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
2answers
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 ...
1
vote
1answer
805 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
196 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
2answers
320 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 ...
5
votes
1answer
571 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} ...
4
votes
1answer
463 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
4
votes
1answer
128 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 ...
2
votes
0answers
392 views

Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
2
votes
1answer
2k views

Will the feasible region always be convex in linear programming? [duplicate]

In linear programming we find a feasible region , is this region always convex? . if a concave region is found where objective is minimization , I think then a solution exists . Advance thanks. ...
2
votes
2answers
347 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. ...
1
vote
1answer
65 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
105 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
1
vote
1answer
352 views

Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...