Questions tagged [linear-programming]

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

1,628 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
83
votes
0answers
2k 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 ...
9
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 ...
6
votes
0answers
796 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
0answers
899 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
117 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 ...
6
votes
1answer
4k 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 ...
5
votes
2answers
52 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
39 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
83 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
0answers
986 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
1answer
313 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
184 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 ...
4
votes
0answers
354 views

Farkas lemma and duality

In his blog, Terence Tao proves the following this version of Farkas lemma. Propsition.   For $i=1,\dots,m$ let $P_i:{\mathbb R}^n\to{\mathbb R}$ be affine linear functions. Then TFAE ...
4
votes
0answers
51 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
94 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
18k 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
1k 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
251 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
163 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
113 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
741 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
443 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
948 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
850 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 ...
3
votes
0answers
23 views

Starting the simplex method from a given basic feasible solution?

I have the following LP. \begin{equation*} \begin{array}{ll@{}ll} {\text{maximize}} & x_1 + x_2 + x_3 + x_4 \\ \text{subject to} & \begin{bmatrix} 1 & -1 & -3 & 1 \\ 2 & 2 &...
3
votes
0answers
38 views

Proximal operator of the function $w \mapsto \max_{i=1}^k a_i^Tw$, for fixed $a_1,\ldots,a_k \in \mathbb R^n$

Let $a_1,\ldots,a_k \in \mathbb R^n$ and consider the convex function $F:\mathbb R^n \to \mathbb R$ defined by $F(w) := \max_{i=1}^k a_i^\top w $. Question. What is the proximal operator of $F$ ? ...
3
votes
0answers
23 views

Best representation/model of a 3D object from multiple observations

I have a sensor that detects the corners of a 3D object. There are 9 corners for that rigid object. The goal is to create the most accurate representation of that 3D object, which can be defined as a ...
3
votes
0answers
42 views

Solve network issue LP-problem

The notation is as follows. Let the network (N, A) be an oriented graph consisting of a number of nodes and edges with a given direction, indexed by $n∈ N = {1, ..., N}$ and $(n,m)∈ A ⊆ {(n,m) :n,m∈ N,...
3
votes
2answers
55 views

Shortest Path Problem Minimization

I am asked to formulate shortest path problem as a min-cost flow problem. The textbook I am using is Gentle Intro to Optimization where it states the max netflow model for graph G with s, t ...
3
votes
0answers
83 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
800 views

Prove that a convex polytope has finitely many extreme points.

$a)$ Prove that a convex polytope has finitely many extreme points. $b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope. Hint : what are the ...
3
votes
0answers
94 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
151 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
0answers
38 views

Inverting Linear System of Inequalities

I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities: $$m\leq m' \leq p+m$$ $$m \leq m'-z' \leq p+m$$ $$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$ (The last one is an equality)....
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
96 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
53 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
0answers
97 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
145 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
154 views

Finding a point with maximum distance from a given point in a polyhedron

We are given the polyhedron $X=\{x:Ax\le b,x\ge 0\}$ and the point $y\in X$. We want to find a point $x \in X$ such that $d(x,y)$ is maximized. The function $d(x,y)$ represents the distance between ...
3
votes
0answers
118 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
61 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
178 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
528 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
85 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
93 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
116 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
166 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 ...

1
2 3 4 5
33