Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
390 views

weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if $x$ and $p$ are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
5
votes
4answers
3k views

Finding the minimal cost edge cover for a bipartite graph

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
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 ...
5
votes
1answer
228 views

Book recommendation to study topics of Linear Programming for self study

I need some reference book suitable for self-study with many solved examples and solutions preferably for exercise questions for following study. Need basic honours undergraduate level text , ...
5
votes
1answer
234 views

Max $P= 7x + 5y + 6z$ Subject to: $x + y − z ≤ 3 x + 2y + z ≤ 8 x + y ≤ 5 x ≥ 0, y ≥ 0, z ≥ 0$

Linear programming problem using the simplex method. Max $P= 7x + 5y + 6z$ Subject to: $$x + y − z \le 3 x + 2y + z \le 8 x + y ≤ 5$$ $x \ge 0, y \ge 0, z \ge 0$ My try: I know how to solve ...
5
votes
1answer
5k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ (...
5
votes
1answer
3k views

How to solve system of equations with multiple constraints?

I have a system of equations that looks like this: $$\begin{array}{rl} a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\ a_1+a_2+a_3&=1\\ a_2&=0.6 \,a_1\\ b_1+b_2+b_3&=500 \end{array}$$ ...
5
votes
2answers
34 views

Rigorous global optimization

The work by Thomas Hales (see enter link description here) before the formal proof solves a number of global optimization problems that need to be solved exactly. The strategy relies on following ...
5
votes
0answers
36 views

Orders of coordinates in a linear subspace

Let $X$ be a linear subspace of $\mathbb{R}^n$. For how many permutations $p$ on ${1,...,n}$ does there exists $x$ in $X$ with $x_{p(1)} < x_{p(2)} < ... < x_{p(n)}$? We can test each ...
5
votes
0answers
75 views

Optimizing value of discrete harmonic function at a given point

Let $n>0$, and let $S_n$ denote the discrete square $S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
5
votes
1answer
3k views

Linear Programming Formulation of Traveling Salesman (TSP) in Wikipedia

I am confused by Wikipedia's Linear Programming formulation of the Traveling Salesman Problem, in say the objective function. Question: If there are n cities ...
4
votes
3answers
3k views

Karush-Kuhn-Tucker condition - Lagrange multiplier

I was maths student but now I'm a software engineer and almost all my knowledge about maths formulas is perished. One of my client wants to calculate optimal price for perishable products. He has ...
4
votes
1answer
10k views

How to write if else statement in Linear programming?

How to write the following if else condition in Linear Programming? If a > b then c = d else c = e d,e are variables. How can we write a linear program without multiplying d and e with binary ...
4
votes
5answers
632 views

Solving matrix equation $AB = C$ with $B (n\times 1)$ and $C (n\times 1)$

I am trying to solve a matrix equation such as $AB = C$. The $A$ is the unknown matrix and I must find it. I know that $B$ and $C$ are $n \times 1$ matrices and so $A$ must be $n \times n$. I can't ...
4
votes
5answers
250 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 ...
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 ...
4
votes
2answers
608 views

Wolves and chicks puzzle

This problem is from the handheld video game, Professor Layton and the Curious Village. I think the solution is very cool, but more than that, I want to know how to show that the minimum number of ...
4
votes
1answer
1k views

How to determine whether a system of linear inequalities has a positive solution or not?

How to determine whether a system of linear inequalities has a positive solution or not? Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms ...
4
votes
2answers
2k views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
4
votes
2answers
4k 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 ...
4
votes
1answer
707 views

Determine which of 8 points make up the 4 corners of a cube's face

I am working on a game program. I have an array of 8 points in 3d space $(X,Y,Z)$ that are the 8 corners of a cube whose $W=H=D$. The 8 points are listed in no particular order. For the sake of ...
4
votes
2answers
402 views

Affine Maps, Matricies, Invertibility, and Equivalence Relations

A mapping $f:\mathbb{R}^n \rightarrow \mathbb{R}^n$ is affine if there is an invertible $n$ x $n$ matrix $M$ and a vector $s \in \mathbb{R}$ such that $f(x)=Mx+s$ for every $x \in \mathbb{R}^n$. Show ...
4
votes
2answers
88 views

Very symmetric convex polytope

Let $C_n$ be the convex polytope in ${\mathbb R}^n$ defined by the inequalities (in $n$ variables $x_1,x_2, \ldots ,x_n$) : $$ x_i \geq 0, x_i+x_j \leq 1 $$ (for any indices $i<j$). Denote by $...
4
votes
1answer
49 views

How is $x = -\text{sign}(c_i)e_i$ the solution to minimize $c^T x$ subject to $\|x\|_1 \le 1$?

From Convex Optimization by Boyd & Vandenberghe: $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & \|x\|_1 \le 1\end{array}$$ Let $i$ be the index such that $\|c\|_{...
4
votes
1answer
47 views

Probabilistic interpretation of optimality gap in Integer Program

Suppose I have an integer program model in the form of a minimization. I noticed that Gurobi (my solver) often finds a very good upper bound (i.e., feasible solution) whereas it takes a significant ...
4
votes
2answers
751 views

Minimization of a sum of taxicab distances formulated as a linear program

Suppose we are given $n$ points $A_1, \dots, A_n \in \mathbb{R}^2$. The task is to find a point $x = (x_1,x_2) \in \mathbb{R}^2$ such that the sum of distances to the points $A_1, \dots, A_n$ in the $\...
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 = $\...
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 ...
4
votes
2answers
130 views

Faster algorithms for convex hulls

I was interested in the following: Given two polyhedra $P_1, P_2$ specified in the form: $$ P_1 = \{x : A_1x \le b_1 \} $$ $$ P_2 = \{x : A_2x \le b_2 \} $$ Whereas $x \in R^n$ and $b_1, b_2$ ...
4
votes
2answers
1k views

Forbidden range for a linear programming variable

I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed. Do you know a way to express this ...
4
votes
2answers
1k views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? $\...
4
votes
2answers
1k views

Simplified nurse scheduling problem

I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which ...
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 ...
4
votes
1answer
186 views

Membership problem for convex cones

Does anyone have a reference for the most efficient or some simple reasonably efficient algorithm for the membership problem for convex cones: Given a finite set of vectors $v_1, ..., v_n$ and a ...
4
votes
2answers
974 views

Rewriting maximization and minimization of $|2x_1-3x_2|$ as linear programs

$$\begin{array}{ll} \text{maximize} & |2x_1-3x_2|\\ \text{subject to} & 4x_1+x_2 \le 4\\ & 2x_1-x_2 \le 0.5\\ & x_1,x_2 \ge 0\end{array} \tag{Problem 1}$$ $$\begin{array}{ll} \text{...
4
votes
2answers
73 views

“Non-traditional” linear programming formulation

I am having trouble coming up with a linear programming formulation for the following question: As head of a sales department, you have to form sales teams to perform site visits to 6 sites: $A, B, ...
4
votes
1answer
320 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
4
votes
1answer
289 views

What gambling/board game or real life thing can (surprisingly) be modelled as a linear programming problem?

So I've taken Linear Programming 101. I've read my textbook, took the test and all that, and - besides all the theory, the nice algebraic interpretations, etc - I've encountered a lot of textbook ...
4
votes
1answer
1k views

Iterative update of pseudo inverse solution

I have an overdetermined linear problem of the form $A x = b$, which is solved in least squares sense using the Moore–Penrose pseudo invers. The issue now is, that over time additional constraints and ...
4
votes
2answers
1k 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
4k views

Choosing Pivot differently in maximization Simplex- and minimization Simplex method?

In maximization simplex, the pivot is the smallest element in the column divided by the rightmost corresponding number. I am stumbling with the Example 3 here with solution that choose the pivot with ...
4
votes
1answer
763 views

Confused about linear programming exercise solution in my textbook

please see this simple linear programming exercise and its solution from my textbook. The task is to convert the prose and matrix to a formal linear programming problem. My answer matched theirs ...
4
votes
1answer
149 views

Custom Nurse Rostering Problem

I've asked this question also on Operations Research Stack Exchange. It's a custom nurse rostering problem: $N$ is a set of nurses; $S$ is the set of shift-type (morning, afternoon, night, rest) $...
4
votes
1answer
185 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}...
4
votes
2answers
146 views

How to prove that 1/3 is the optimal solution for the muffin problem with 5 students and 7 muffins?

The Muffin Problem Definition Let there be $m$ muffins and $s$ students. The problem is to divide the muffins into pieces where every student gets exactly $\frac m s$ muffin, such that the size of ...
4
votes
1answer
1k views

Understanding complementary slackness

I've chosen a simple example to help me understand duality and complementary slackness. Suppose we have linear program: $$Maximize\quad 5x_1+x_2\quad s.t$$ $$2x_1+x_2 \le 6$$ $$x_1+x_2 \le 4$$ $$2x_1+...
4
votes
1answer
406 views

Equivalence of a binary linear program and its relaxation

We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite ...
4
votes
1answer
398 views

What formulation for any 0-1 knapsack problem has the tightest LP relaxation?

Since the knapsack problem with integer variables can be reduced to a binary variable case, consider the problem $$\max\{cx:x\in K\}$$ $$ K:=\left\{ x\in \{0,1\}^n: \sum_{i=1}^n a_ix_i\le b \right\} $$...
4
votes
1answer
270 views

Prove that an edge of a polyhedron is a line segment

Preliminaries Let us define $\mathbb{N}_n=[1,n]\cap\mathbb{N}^+$ for all $n\in\mathbb{N}^+$. $\ $ A polyhedron is an intersection of halfspaces, i.e., a set of the form $\{x\in\mathbb{Q}^n\mid Ax\le ...
4
votes
1answer
4k views

Measuring rotation and translation differences between two matrices

I am developing a docking application in which I want to have for every step the difference between the target transformation matrix and the user's transformation matrix. Now I don't have any problem ...