# Questions tagged [linear-programming]

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

1,442 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
991 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 ...
573 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 ...
597 views

### Solving $Ax = b$ for non-negative $x$ given boolean matrix $A$ and non-negative $b$

I am trying to solve $Ax = b$ with the following properties: $A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$ $A$ is of size $m \times n$ where $m \ll n$ ...
1k views

### Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
851 views

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 ...
182 views

### Linear algebra characterization of when half-spaces' intersection is bounded.

Suppose a finite set of $m$ half-spaces $H_i$ in $\mathbb{R}^n$ are described by equations $$\mathbf{\ell}_i \cdot \mathbf{x} \leq 1.$$ for $1\leq i \leq m$. If $L$ is the $m\times n$ matrix ...
50 views

### Efficient Batched Linear Programming

Suppose I have a polyhedron given as $$Ax \le b , x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$$ and I have a collection of functions $c_1^Tx , c_2^T x ,\ldots, c_k^Tx$ that ...
92 views

### I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
17k views

### How to find all basic feasible solutions of a linear system?

I'm trying to solve this problem but need some help getting started. The problem asks to find all the basic feasible solutions of the following system: \begin{equation} -4x_2+x_3=6 \end{equation} \...
1k views

### Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
947 views

### Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t$$ subject to:...
89 views

### Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
201 views

### Parameterizing equilateral polygons

I'm not exactly sure how to describe what I want, so if I butcher terms, please forgive me :) I want to "parameterize" the space of simple irregular equilateral polygons with n sides, or at least a ...
157 views

### Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
783 views

36 views

### On the Fundamental theorem of Linear Programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
18 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 ...
41 views

### Showing a disc has infinitely many extreme points

EDIT: Stuck on a part of a problem for a Linear programming course. I want to show the unit disc is not a convex polytope and my strategy is to show that it has infinitely many extreme points. How ...
82 views

### Determining if a Vector is a member of a Convex Hull

Edit: Here is how the following sets are created: $S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear ...
28 views

### linear program, why is there an outgoing arc such that $d(s,v) = w(s,v)$

If any other information is needed, please feel free to ask me. I'm beginning my learning in graph theory and in optimization. Let's call $D = (V,A)$ a directed graph. $w : A \to \mathbb R$, arc ...
35 views

### Reducing the Eulerian cycle problem in a mixed graph to a maximum flow problem

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is ...
46 views

### How to quickly determine if a linear program is feasible?

I have a series of linear programs in canonical form $$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ and I need to ...
675 views

### Shortest path between nodes in a graph with multiple sources and destinations? (No collisions.)

Dijkstra's algorithm is a well-known method for finding the shortest path between two nodes in a graph. For instance, let's say that we have a graph like this: base graph Imagine that we want to ...
86 views

### Why does the Canonical Form of linear programming have non-negativity?

Aren't the non-negativity constraints special cases of the general constraints? Isn't $$x_1 \ge 0$$ just $$-1 \cdot x_1 + 0 \cdot x_2 \le 0?$$ Then you could just summarize the general form of ...
85 views

### Can I obtain a unitary block matrix from any invertible matrix?

Suppose A is any square invertible complex matrix. Then $$C = \left[ \begin{array}{c|c} 0 & A \\ \hline A^{\dagger} & 0 \end{array} \right]$$ is a Hermitian matrix. My Question: Is ...
108 views

96 views

### Existence of solution of linear system with equality and inequality constraints

Given matrices $A$ ($n \times k$) and $C$ ($m \times$k), and vectors $b$ and $d$, I want to know if there is a value of $x$ that solves the two constraints below: \begin{array}{c} A x = b \\ ...
296 views

### What is the role of the recourse variable in stochastic programming?

What is the role of recourse variable in stochastic programming? I often see two-stage stochastic programming problems with recourse, written as follows: Stage 1 \begin{equation} \begin{array}{...
152 views

### Motivation behind Lagrangian duality

As the title states, what is the motivation behind the Lagrangian duality in integer programming? I tried looking up online references including the post: BigPicture Lagrangian, KKT, Duality, and also ...
434 views

### Correctness of the artificial constraint method (dual simplex)

The artificial constraint method is used to find an intial basis to start executing the dual simplex algorithm to solve a linear programming programming problem (say we want to minimize $c^tx$). The ...
54 views

### Convex Polytope

My Linear Programmation book tells me to consider the closed and limited Convex Polytope defined as $$S=\left \{ \right.\bar{x}:A\bar{x}=\bar{b} ,\bar{x}\geq 0\left. \right \}$$ But , does this ...
81 views

71 views

### Linear programs and integer solutions

We are given the following linear program: minimize $\mathbf{1}^T x$ subject to $Ax\geq \mathbf{1}, x\geq \mathbf{0}$. We know that $A\in\{0,1\}^{m\times n}$, and that each row and column contains ...
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$ ...
A project involves three activities $a_1, a_2$ and $a_3$. $a_3$ can start only after $a_1, a_2$ are completed. The amount of work done by a single worker in a day for the activities are 2, 3 and 1 ...