Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
3
votes
2answers
226 views

Need help defining a Quadratic Programming problem

I have an optimization problem which should be solvable with Quadratic Programming: There are $n$ multiplication coefficients $c_i$ for which optimized values are searched. The coefficients are ...
0
votes
0answers
19 views

How to find the $K$-nearest neighbor vertexs in a polyhedron defined by a set of linear inequalities?

Consider a polyhedron $\mathcal{P}$ defined by a set of linear inequalities, i.e., $$\mathcal{P} = \left\{ x \in \{0,1\}^N \mid Ax\le b \right\}$$ Suppose $\mathcal{P}\neq \emptyset$. If I have a ...
1
vote
1answer
751 views

Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
0
votes
1answer
83 views

How to find the general solution set to a constrained system of linear equations

Consider the following general system of linear equations $$ \begin{pmatrix} a & -b\\ -c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} v \\ w \end{pmatrix} $$ where $...
0
votes
1answer
16 views

Binary Matrix with constant row and column sum contains a permutation matrix

The following problem was given as a homework problem, so I am not necessarily asking for a full solution, but rather a good hint on where to start. A chess board, where some of the $64$ cells ...
0
votes
3answers
41 views

How to solve a system of linear inequalities?

I am working on the following exercise: Find a solution to the following system or prove that none exists: \begin{align} x_1-x_2 &\le 4\\ x_1-x_5 &\le 2\\ x_2-x_4 &\le -6 \\ x_3-...
0
votes
2answers
48 views

How to find a solution to an inequality system?

I need to find a solution to the following system of linear inequalities: \begin{align} x_1-x_2 &\le 1\\ x_1-x_4 &\le -4 \\ x_2-x_3 &\le 2 \\ x_2-x_5 &\le 7 \\ x_2-x_6 &\le 5 \\ ...
0
votes
1answer
69 views

Why can't Simplex Method solve big equations? Have I forgot something?

I just wrote a Simplex Method in pure C-code and I have tested it. It works for the objective function: $$\max: c^T x$$ With subject to: $$Ax \le b \\ x \ge 0$$ Here is an example: ...
0
votes
1answer
19 views

Reformulation logical AND in integer programming maximization problem

Suppose we have variables $x_1,x_2,y \in \{0,1\}$ such that $y=1$ if and only if $x_1 = x_2 = 1$ and we want maximize the value of $y$. I know that this reduces to the following Integer programming ...
1
vote
1answer
801 views

Set of Feasible Directions

I don't even know what to do for the first part. How do you even find all the feasible directions of a particular Set...? Then how do you proceed to finding basic directions?
0
votes
0answers
27 views

Questions about Simplex method - How should I devide?

I have made a simplex method algorithm in C language and I have some questions about it. Assume that we have this objective function. $$max: z = c^T x$$ At the subject to: $$Ax <= b \\ x >= 0$$ ...
3
votes
1answer
101 views

Null Variable in linear programming

Let $P=\{x\in\mathbb{R}^n|Ax=b,x\geq0\}$ be a nonempty polyhedron, and let $m$ be the dimension of the vector $b$. We call $x_j$ a null variable if $x_j=0$ whenever $x\in P$. (b) prove that if $x_j$ ...
0
votes
2answers
85 views

Can linear programming be used to solve Ax = b equations?

Assume that we have a system $Ax = b$ and we want to solve that with constraints. Can linear programming be used to solve the $x$ from $Ax = b$? Assume that we have the objective function $$max : ...
0
votes
1answer
26 views

Maximisation of the absolute value of a linear function subject to bound constraints: Am I wrong?

I have the following optimisation problem: $\max |a_0 + a_1x_1 + \dots + a_nx_n |$ subject to bound constraints $\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u.$ According to this previous post ...
0
votes
1answer
51 views

Prove in a $4 \times 4$ battleship game the expected payoff of player one is $\frac{3}{4}$

A battleship game is played on a $4 \times 4$ matrix, player one can place their domino(that takes up $2$ adjacent spaces) in one of $24$ places(There are $3$ places in each row and each column it can ...
0
votes
0answers
25 views

Let A be an $m\times n$ payoff matrix of a two person zero sum game. If the avg entry in a column $\ge 5$. Show row player's expected winnings $\ge 5$

Let A be an $m\times n$ payoff matrix of a two person zero sum game. If the avg entry in a column$\ge 5$. Show that the row player's expected winnings $\ge 5$ I'm assuming the proof has to do with ...
1
vote
2answers
683 views

Disjunction of conjunction in linear programming

I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression: R = (a1 and b1) or (a2 and b2) or (a3 and b3)...
-1
votes
1answer
32 views

Combination of AND OR in Linear Programming

I have three binary variables: $x,y,z$. I want to define $U$ as follows: $$U = x \wedge (y \vee z)$$ Following this, I have already tried defining $$yz = y \vee z$$ and then, doing $$U = x \...
1
vote
1answer
30 views

deciding to insert a variable a to the basic set in the next step and exclude 𝒂 basic one 𝒃

Let's say you are in the middle of applying the Simplex Method to an LP problem. You've reached a tableau and by checking the sign of the objective coefficients you decided to insert a variable a to ...
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 ...
1
vote
1answer
26 views

Suppose a two digit whole number is divided by the sum of its digits, largest and smallest possible values

Suppose a two digit whole number is divided by the sum of its digits, what are the largest and smallest possible values? So we can write a two digit whole number as $n = 10a+b$ where $1 \leq a,b \leq ...
0
votes
0answers
46 views

Solving Ax=b with matrices (bigger than 2 by 2 matrices)

I have been working on creating a program that solves linear systems of equations for the Jacobi and Gauss-Seidel iterative methods. (Link to the methods: https://www.cis.upenn.edu/~cis515/cis515-12-...
1
vote
1answer
19 views

How to solve linear equations with structured matrices?

Suppose $\mathbf{x}\in R^{m\times 1}$, $\mathbf{X} = [\mathbf{x}\, \mathbf{x}\, \cdots]^\top\in R^{nm\times 1}$ and $\mathbf{b}\in R^{nm\times 1}$ and $\mathbf{A}\in R^{nm\times nm}$. How to solve \...
0
votes
0answers
26 views

Linear independence and simplex

Let $X:=\{x \in R^n |Ax=b \}$ and $I \subset \{1,...,n\}$ such that, $b\in C([\{a_i\}_{i \in I}$]). Prove that for every set $B \subset \{1,...,n\}$, such that $\{a_i\}_{i \in B}$ is linearly ...
0
votes
1answer
31 views

Optimize absolute value $\min |x| + |y|$

How do you convert $\min |x| + |y|$ to a linear program? Is this method correct? $$\min w + z$$ $$w >= x$$ $$w >= -x$$ $$z >= y$$ $$z >= -y$$
2
votes
1answer
50 views

Show that if Phase I of the two-phase method ends with an optimal cost of zero then the reduced cost vector will always take the form $(0, 1)$

Consider a linear programming problem of the form: minimize $c^Tx$ subject to: $Ax=b$, $x\geq0$ where $A$ is an $m\times n$ matrix with linearly independent rows. Show that if Phase I of the two-...
1
vote
0answers
19 views

Prove that the Basis Solutions of a Linear Programming Problem are the Extreme Points of the Polyhedron of Allowed Solutions

Given a system of $$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$ where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean ...
0
votes
1answer
226 views

Help solving linear programming problem with simplex method

My friend needs this problem solved, but she doesn't know how. She asked for my help, but the problem is - I don't know either. Could somebody guide me through the process, please?
0
votes
3answers
996 views

How can I linearize the distance from two points?

I'm studying Operations Resarch and the professor give us the following problem: • There is a 10*10 matrix in which there are 20 villages on random coordinates. • We have to drop two supply packages (...
0
votes
1answer
57 views

An Application of Farkas' Lemma

The Farkas' lemma I know is: Exactly one of the following systems has a solution. \begin{equation} \left\{ \begin{array}{l} Ax=b,\ x\geq0 \\ A^Ty\geq0, \ y^Tb<0 \end{array}...
1
vote
1answer
47 views

Formulate the mathematical model to find the optimal solution

A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
0
votes
0answers
18 views

total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
0
votes
0answers
19 views

LPP: Simplex Method - Interpreting Solutions

Having trouble keep all the cases straight in my head for the Simplex method in Linear programming problems. What does it mean for a Simplex table solution to be feasible but not optimal? Both ...
1
vote
0answers
40 views

Linear transformation of overdetermined linear system

Assume that we have the following over-determined linear system \begin{cases} z_{1}=c + \phi z_0\\ z_{2}=c + \phi z_{1}\\ \dots\\ z_{n} = c + \phi z_{n-1} \end{cases} with $n>2$ and all $z_{0}, \...
1
vote
0answers
25 views

Find the lowest difference in exchanged value

I was wondering if this type of problem can be modelled with Linear Programming or any other approach that much more efficient. Let say I've 5500 in original currency. I want to convert to other ...
0
votes
0answers
29 views

Linear programming such that feasible solution gives optimal solution to another

Let us say that we have a linear program $P={ (min C^tx | Ax=b,x\geq0)}$ Assume that $(P)$ has an optimal solution. Write a system of linear equations and inequalities $(P_1)$ such that any feasible ...
1
vote
1answer
20 views

Minimizing a General n-Dimensional Linear Program

I am currently studying linear programming and am attempting to solve: minimize $c^Tx$ subject to $\sum_{i=1}^{n}x_i=0$, and $\sum_{i=1}^{n}x_i^2 = 1$. From the second constraint I know that: $-1\...
1
vote
1answer
31 views

Linear program with unknown constraints(just extreme points)

Suppose you are given a set $F$ consisting of $n$ mutually distinct bounded points in $\mathbb{R}^d$. We can define a linear program \begin{align}\max \ c^Tx \\\text{s.t.}\ \ x \in \text{Hull}(F)\...
0
votes
1answer
18 views

Find $y \in \operatorname{conv}(\{x_{1}, x_{2}\})$, so that $z \in \operatorname{conv}(\{y, x_{3}\})$

Let $z \in \operatorname{conv}(\{x_{1}, x_{2},x_{3}\})$. Find $y \in \operatorname{conv}(\{x_{1}, x_{2}\})$, so that $z \in \operatorname{conv}(\{y, x_{3}\})$ My idea so far: since $z \in \...
0
votes
0answers
31 views

How to show that the lpp has optimal solution without solving it

I have got to maximize $$Z=x+2y-3z+4w$$ subject to constraints $$x+y+2z+3w=12$$ $$y+2z+w=8$$ $x,y,z,w\geq 0$ . The question asks to show without actually ...
1
vote
0answers
70 views

Maths (ILP) puzzle from a programming contest

This programming contest puzzle concerns itself with "cards", each of which bears a certain pattern of either one circle, one square, one triangle, two circles, two squares, etc. up to three circles, ...
0
votes
1answer
54 views

Cannot Understand solution: Inconsistent systems of linear inequalities proof.

I'm trying to understand the solution to this question in Bertsimas 4.29: Question: Let $a_1,....a_m$ be some vectors in $R^n$ with $m>n+1$. Suppose that the system of inequalities, $a_i'x \geq ...
1
vote
1answer
843 views

Conditions for uniqueness of solution to a linear system of equation

Consider a $n\times n$ M-Matrix $\mathbf{A}$ and a $n\times n$ non-negative and non-zero matrix $\mathbf{B}$. Also, let $\mathbf{x}$ and $\mathbf{b}$ be two (non-zero) n-column vectors. I am looking ...
2
votes
2answers
64 views

Formulating Linear Program: Separating Hyperplane

Consider a polyhedron $P$ that has at least one extreme point. Suppose that we are given the extreme points $x^i$ and a complete set of extreme rays $w^j$ of P. Create a linear programming problem ...
1
vote
1answer
72 views

Breakdown an integer value to an array of integer maintaining the sum

I am working on a project where I need to breakdown an integer value according to an array of percentage values. My end array must contain integer value and the sum of the array must be equal to the ...
1
vote
0answers
50 views

Simple Linear Algebra/ Linear Programming Proof: Proving Existence of Vector that satisfies Properties

Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $x_j$ is ...
8
votes
1answer
1k views

Blotto game variation

My smart friend ZWX challenged me to solve the "brainteaser" below, but to my surprise, the problem seems highly nontrivial as I took a closer look. Anyway, the question goes: In a game, both you ...
0
votes
1answer
67 views

Two conditional constraints (either or neither) for integer binary programming [closed]

Not sure how to go on about finding this constraint. The constraint asks for; either both or neither of $x_1$ and $x_2$ should appear. What I have so far is that y can be either binary values $0$ or ...
0
votes
0answers
9 views

How to prove that $c^Tx(\mu)$ is strictly decreasing with $\mu$ in interior point method for LP

Consider the Primal-Dual problem, (P)min $c^Tx$ s.t. Ax = b, x $\geq 0$ (D) max $b^Ty$ s.t. $A^Ty + s = c$, s $\geq 0$ The log-barrier function for (P) is : min $c^Tx - \mu \sum_{i=1}^n ln(x_i)...