Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
109 views

question about linear programming minimization

(P) $\min z=x_1+x_2$ subject to : $ x_1+2x_2 \geq 4$ ( equation 1) $2x_1+x_2\geq6$ (equation 2) $-x_1+x_2\leq1$ (equation 3) $x_1>=0 ,x_2\geq0 $$ $ I'm trying to solve this using two-...
0
votes
4answers
1k views

Arbitrage sports betting [closed]

Player A vs Player B. Bookie 1 offers 1.36 odds on player A winning. Bookie 2 offers 5.5 on player B winning. We have $1000 in total to bet. How would you place your bets such that ...
16
votes
5answers
10k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
8
votes
2answers
13k 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 ...
15
votes
3answers
28k 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 ...
13
votes
2answers
394 views

Polygons with 2 diagonals of fixed length (part two)

In this question of mine Polygons with two diagonals of fixed length I've presented the following particular polygon $P$ and I've asked the following question: is it possible to shorten one or ...
8
votes
2answers
5k 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, & ...
6
votes
1answer
1k 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 ...
6
votes
2answers
8k views

How to covert min min problem to linear programming problem?

I have the following problem: set $P=\{1,2,3...,n\}$ for index $i$, set $K=\{1,2,3,...,m\}$ for index $k$. Value $B_i^k$ is indexed by both $i$ and $k$, while value $l_i$ is indexed by only $i$. Here ...
5
votes
4answers
7k 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 ...
11
votes
1answer
456 views

Maximize the trace of a matrix by permuting its rows

I have been struggling with a combinatorial problem that eventually translates to the following: Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace. ...
6
votes
2answers
5k views

why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic?

Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an articial variable becomes nonbasic, it need never again become basic. Thus, when an articial ...
4
votes
2answers
554 views

Is there an effective algorithm to solve this binary integer linear programming?

I am an applied math undergraduate student. On my project, I come across an integer linear programming question as follow: Given $x_0,x_1,...,x_n$: $\forall$ i $\in$ [0,n], $x_i$ = 0 or 1 min Z = $\...
10
votes
1answer
6k views

Strict inequalities in LP

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

Minimizing the sum of absolute values with a linear solver

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, ...
5
votes
2answers
7k 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
0answers
105 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?
3
votes
1answer
847 views

Maximizing positive components in solution vector of linear programming problem

Part (a) looks to maximize positive components in the solution vector x by solving a related LP. Part (b) looks to do the same with only 1 LP. I am familiar with solving LPs, but I am not sure how to ...
3
votes
1answer
943 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 ...
1
vote
2answers
2k 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
173 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 ...
9
votes
1answer
2k views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
8
votes
4answers
11k views

How can not-equals be expressed as an inequality for a linear programming model

I have this linear programming model I'm building but one of the constraints needs to specify that the solution's basic variables need to all be different from one another. This is an integer linear ...
7
votes
2answers
2k views

Linear programming algorithm that minimizes number of non-zero variables?

I have real world problems I'm trying to programmatically solve in the form of $$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$ Subject to \begin{align} & a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} =...
7
votes
2answers
9k views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
5
votes
1answer
5k views

How can I determine B-inverse from an optimal tableau of a LP?

(This is NOT a homework question, I am reviewing for my upcoming exam) Given this linear program: and this optimal tableau: I am attempting to determine $B$ inverse using the table above. From the ...
5
votes
1answer
2k views

Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...
4
votes
1answer
175 views

Show that any linear function $f:\mathbb{R}^n\to\mathbb{R}$ is of the form $f(x)=a^Tx$ for some vector $a\in\mathbb{R^n}$.

$a)$ Let $a$ be a (column) vector in $\mathbb{R}^n$. Show that the function $f(x)=a^Tx$ is linear function from $\mathbb{R}^n$ to $\mathbb{R}$ $b)$ Show that any linear function $f:\mathbb{R}...
3
votes
1answer
1k views

Reconstructing an optimal Simplex tableau from an optimal solution

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

Minimizing absolute differences between n values under constraints on sums of these values

I have 15 unknown integer values $x_i$. I know that: $$\sum_{i=1}^5 x_i = 25 $$, $$\sum_{i=6}^{10} x_i = 32 $$ and $$\sum_{i=11}^{15} x_i = 41 $$ I wish to identify 15 integer $x_i$ that minimize $$\...
3
votes
1answer
615 views

Farkas Lemma Question with strict inequality

I have a question which I thought that can be solved by Farkas Lemma, but I could not manage it. Prove that only one of the systems has a feasible solution, where $A$ is an $m \times n$ matrix, $C$ ...
2
votes
1answer
716 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
2
votes
1answer
607 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)=-\lambda ...
1
vote
1answer
7k 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
1answer
38 views

Adding a combination of and + or operator constraint in Linear Programming

I have a list of paired variables(paired_list) like below and a resultant variable(my_res). paired_list = [[a,b],[c,d],[e,f],...]. Here a,b,c,d,e,f are also ...
1
vote
1answer
3k views

Solve Karush–Kuhn–Tucker conditions

solving a constrained optimizing problem with equality constraints can be done with the lagrangian multiplier. (http://en.wikipedia.org/wiki/Lagrange_multiplier) This approach leads to a system of ...
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? $$...
6
votes
1answer
589 views

Integer linear programming constraint for maximum number of consecutive ones in a binary sequence

Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in ...
6
votes
1answer
2k views

Computationally proving a linear programming solution is unique?

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, ...
5
votes
2answers
8k views

How Can $ {L}_{1} $ Norm Minimization with Linear Equality Constraints (Basis Pursuit / Sparse Representation) Be Formulated as Linear Programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
5
votes
2answers
560 views

minimize $c^tx$ subject to $Ax=b,x\ge0$ dual problem

Consider the linear program to minimize $c^tx$ subject to $Ax=b,x\ge0.$ Write the dual problem. Drew Brady user helped me to do this but I still have doubts about it. First off, the lagrangian ...
5
votes
1answer
192 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
4k 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 ...
4
votes
2answers
15k views

bounded vs. unbounded linear programs

Consider a (linear) optimization problem of the form "maximize $c^{\top}x$ subject to $\varphi(x)$". Consider the following definitions: The program is called unbounded iff it is feasible but its ...
3
votes
2answers
936 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}...
3
votes
1answer
468 views

Dual of an equality constraint in MIP

In a mixed integer programming question how one may find the dual of the equality constraint? As example: $min \quad C^T X$ $s.t. \quad aX\leq b$ $\qquad eX=d$ $\qquad X\in integers$ How to find ...
3
votes
0answers
370 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 ...
3
votes
1answer
614 views

Is A Simplex Method Appropriate for Solving Nash Equilibria?

I've been attempting to teach myself some game theory and in the process, some linear programming. While muddling through this, I've been attempting to use a variety of simplex methods to attempt to ...
3
votes
1answer
1k views

Need help finding unknowns in simplex tableau.

I need help with this homework problem. The objective is to maximize $2x_1 - 4x_2$, and the slack variables are $x_3$ and $x_4$. The constraints are $\le$ type. Tableau $\begin{matrix}z & x_1 &...
3
votes
2answers
6k 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) &...