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

learn more… | top users | synonyms

13
votes
0answers
334 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 ...
6
votes
0answers
96 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
655 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} ...
4
votes
0answers
69 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
77 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
548 views

How to Minimize A Function Where The Number of Variables is Unknown

I have a standard linear programming problems I want to solve: $$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
3
votes
0answers
126 views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
3
votes
0answers
69 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 ...
3
votes
0answers
79 views

Converting a max-min problem to a max problem with a constraint

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ...
3
votes
0answers
174 views

A basic question related with the solutions of linear programming problems

I have to select one option from the problem statement given below. Which of the following statements is true in case of linear programming. $1$: An optimal solution exists at extreme points of a ...
3
votes
0answers
316 views

Nested optimization problems solving using mixed integer linear programming

Let us have two vectors of decision variables, $\mathbf{x}$ and $\mathbf{y}$, two linear objective functions, $F \left( \mathbf{x}, \mathbf{y} \right)$ and $f \left( \mathbf{x} \right)$, and two sets ...
3
votes
0answers
104 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
3
votes
0answers
304 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 ...
3
votes
0answers
62 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: ...
3
votes
0answers
77 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
3
votes
0answers
271 views

Bender's Decomposition for Mixed Integer Programs

Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1). $LP_1$ has the form ...
2
votes
0answers
62 views
+50

When might some a variable leave the basis?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
2
votes
0answers
33 views

What is the subscript of the max notiation stating?

I am a physics graduate interested in moving into the field of AI. My knowledge of pure maths is limited, leading to difficulties in even understanding notation in the subject. I do not understand ...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
2
votes
0answers
30 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
2
votes
0answers
25 views

Can the non-uniqueness of a linear program's dual feasible set be exploited?

I was originally under the impression that a primal LP had a single corresponding dual feasible set. However, it is possible to alter the primal to an algebraically equivalent form which has a ...
2
votes
0answers
32 views

Modeling Objective function using mixed integer programming formulation

I have the following objective function max 2x1 -2f(x2), where f(x2) = 3 if x2 = 0 and f(x2) = 2-5x2 if x2 > 0; can anyone help me formulate it using binary ...
2
votes
0answers
24 views

Tangential surface of an extreme point of a convex subset of a simplex

Suppose that there is a convex set (polyhedra) $H$ which is a convex subset of a simplex $G = \{x\in R^d ~|~ \sum_{i=1}^d x_i=1, x_i \ge 0, i=1,2, ..., d \}$. Clearly, $H$ has extremal points $x^*$ ...
2
votes
0answers
82 views

linear problem with $\|.\|_\infty$ and $\|.\|_1$ norm constraints

I have a question regarding a straightforward linear algebra problem, yet the solution is (at least for me) not trivial. Assume the sequences $\phi_i$ with coefficients $\phi_i[n]\in\mathbb{R}$, and ...
2
votes
0answers
37 views

working with negative sign restriction in linear programming

I am new in optimization. I want to solve a maximization problem using simplex method whose one of the decision variable is negative sign constraint. I know how to process for positive sign ...
2
votes
0answers
69 views

Solve constrained system of linear equations from samples of a reference function

I have a system of $2n$ linear equations in $2n$ unknowns represented by the standard matrix equation: $$Ax = b$$ Where the solution vector $x = (p_1, ..., p_n, q_1, ..., q_n)$ represents real ...
2
votes
0answers
1k views

Primal and dual problem (Optimal solution) - Operations research

I'm currently studying operations research and I want to know and understand how we find an optial solution to the dual problem with minimum effort. Lets say we have this primal and dual problem: ...
2
votes
0answers
92 views

What subjects properly belong in operations research as their “owning” discipline?

Warning: This is a soft question, hence I would make it a wiki-community post if I could. Operations Research involves a broad swath of disciplines, ranging from probability and statistics/stochastic ...
2
votes
0answers
97 views

Finding number of basic solution based on different cases

I need help understanding the question. Consider the polyhedron P = {x in R^n | Ax = b x => 0}, where A in R^mxn and b in R^m. Assume that any m columns of A are linearly independent. (a) Suppose ...
2
votes
0answers
45 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
2
votes
0answers
610 views

Linear program for way optimization with unusual constraints

I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com: The goal of the game is to pick up ...
2
votes
0answers
81 views

Lagrange Multipliers for linear functionals

Say I have a Banach-space $X$ and linear (!) functionals $f,g$, and I'm trying to solve the constrained optimization problem $$\max~f(x)\quad \mbox{s.t.}~g(x)= 0,~\Vert x\Vert\le 1.$$ Suppose I can ...
2
votes
0answers
289 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
2
votes
0answers
165 views

Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
2
votes
0answers
54 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
2
votes
0answers
228 views

mathematical model of an assignment/scheduling problem

I am solving a scheduling problem and I am able to abstract it into an assignment problem of assigning 45 machines to 42 jobs. the assignment problem was given as having 14 jobs, each with 3 tasks and ...
2
votes
0answers
54 views

Simple Linear Program Problem in Constrained Optimization

Here is a subproblem I am having difficulties with: $$d = \arg\min_x \ c^Tx$$ subject to $$x: \sum_{i=1}^{n} x_i = 0,\quad x_i \ge -b_i$$ for some $b \in \mathbb R^n$. So I'm looking for an ...
2
votes
0answers
41 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 ...
2
votes
0answers
294 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
2
votes
0answers
55 views

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)?

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)? I'm having some problems with it. Please clarify it. I have posted ...
2
votes
0answers
139 views

Convert a problem o minimizing a function to linear programming problem in standard form

I have to 1) convert a problem o minimizing a function to linear programming problem in standard form. It is something new to me. Can somebody explain it to me? $$\min(\mathbb{R}^2\ni(x,y)\rightarrow ...
2
votes
0answers
36 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
2
votes
0answers
54 views

Rayleigh Quotient variant?

If $A$ is a covariance matrix and I want to get $\max X^TAX$ where each value of $x$ is between -1 and 1. Is there a closed-form solution for this? I understand when $X^TX = 1$ this becomes the ...
2
votes
0answers
143 views

Post-optimality analysis: Change in one of the constraints

Consider the LP: \begin{array}{rccc} \max& \quad -3x_1&-x_2& & \\ \text{s.t.}& \quad 2x_1&+x_2 &\leq 3 \\ & -x_1&+x_2 &\geq 1 \\ &&x_1,x_2 &\geq ...
2
votes
0answers
23 views

Determining maximum number of groups - maybe Linear Programming

Given a set D dogs, C cats, and B birds, for each dog d in D, there is a set c(d) which indicates the set of cats that dog d likes and a set b(d) birds that dog d likes. How do I find the maximum ...
2
votes
0answers
76 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
2
votes
0answers
62 views

Assigning jobs to minimize cost - Linear programming

I'm stuck trying to solve this linear programming question. You want to make a website with a list of features F, which are n elements long. Each feature has a corresponding value for how long it'll ...
2
votes
0answers
139 views

Big M constraint question

I have a question regarding using Big M constraints to solve the following problem: Given: $a, b \ge 0$ and integers. $$2a + 5b \le 17\\ a + b \le 5\\ 3a + 6b \le 20$$ For at least two of the ...
2
votes
0answers
241 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
2
votes
0answers
212 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...