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
56
votes
0answers
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 ...
8
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
0answers
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$ ...
6
votes
1answer
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 ...
6
votes
0answers
851 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} f(x)p(x)...
6
votes
0answers
115 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
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
73 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
1answer
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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} \...
4
votes
1answer
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 ...
4
votes
0answers
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:...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
783 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where $c,a\in\mathbb{R}^{M\...
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?
4
votes
0answers
666 views

fundamental theorem of linear inequalities

Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...
4
votes
0answers
413 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
4
votes
0answers
850 views

Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
4
votes
0answers
766 views

Real-time linear programming

I'm going to implement in C a light-weight embedded LP solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programs with ~6-60 variables and ...
4
votes
2answers
174 views

L1 minimization problem with nested sums as LP problem

I've been trying to solve this problem but I have an issue with the fact that there is a sum under each absolute value. I'm trying to convert this minimization problem (with respect to $x, y_1, \dots,...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
108 views

Derive the supremum of a function

Consider any vector $\mu\equiv(\mu_1,...\mu_M)\in \mathbb{R}^M$. Take $G: \mathbb{R}^M\rightarrow \mathbb{R}$ with $G(a)\equiv \mathbb{E}_{\mathbb{P}}(\max_{k\in \{1,...,M\}}V_k+a_k)$ for any $a\...
3
votes
0answers
55 views

Formulate linear program into two-stage stochastic LP

Given the linear program: $Z = min_{x\geq 0}\ 2x_1 + x_2 + E_{\ k \ =\ (k_1, k_2)} \left\{\max(k_1 - x_1, 0) + \max\left\{max(k_1-x_1,0) + k_2 - x_2, 0\right\} + \max(k_1 - x_1, 0) + \max(k_2-x_2, 0)...
3
votes
0answers
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 \\ ...
3
votes
0answers
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}{...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
81 views

actually USING the lagrangian dual to solve a problem

I don't get the maximisation bit in the dual problem... Let's consider the standard form LP: minimise $c^\top x$ subject to $Ax = b, x \geq 0$ This has lagrangian $$\mathcal{L} = c^\top x +...
3
votes
0answers
113 views

How to linearize a not linear program with excel?

I want to use Excel solver to solve the following integer linear program: A company wants to select $p$ locations among a set of $m$ possible sites for constructing polluting plants in a ...
3
votes
0answers
155 views

Can someone please explain Convex Optimization without Hessian Matrices?

I need help. In my class we're not using Hessian matrices with our convex optimization. I don't really understand how to find out if it's concave or convex. All the videos I look at and articles I ...
3
votes
2answers
75 views

Solving linear programming problem with given information

I want to find the optimal solution to a following linear programming problem: $$8x_1+120x_2+114x_3\to \min$$ $$x_1+7x_2+3x_3\geq 4,$$ $$x_1+5x_2+5x_3\geq 5,$$ $$x_1+3x_2+10x_3\geq 9,$$ $$x_1+2x_2+...
3
votes
0answers
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 ...
3
votes
1answer
597 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$ ...
3
votes
0answers
83 views

Solving a linear programming problem with different constraints

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