0
votes
0answers
17 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
0
votes
1answer
26 views

Linear problem: maximizing net income

Problem: A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash avaliable and machine capacity. Each unit of the first ...
1
vote
1answer
29 views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where ...
0
votes
0answers
16 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...
1
vote
0answers
55 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
1answer
49 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
2answers
34 views

How to introduce flat cost of flow over a node using mixed integer programming.

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program. \begin{array}{ll} \text{minimize} ...
0
votes
1answer
26 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
0
votes
1answer
38 views

How to transform a maximizing objective function which contains a max operator to a standard LP form

My Optimization objective function looks like this: $\max\quad(c_1 x_1 + c_2 \max\{x_2, x_3, x_4\})$ all variables, $x_i$ are binary variables. There are also some linear constraints such as $a_ix_1 ...
2
votes
1answer
29 views

Simple minimization problem

Suppose we want to execute a program on a processor which can run in three different modes. Each mode can be describe by a pair $(E,\tau)$ where $E$ denotes the energy consumption per cycle (in nJ) ...
1
vote
1answer
28 views

Can Gomory's cutting plane be used to solve Mixed Integer Linear Programs?

Do you know if Gomory's cut can be used to solve MILP problems ? I have read that Gomory's cut is useful when all variables are integer, but what if just some of them are integer ? Is is necessary ...
2
votes
0answers
25 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 ...
0
votes
0answers
49 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
0
votes
1answer
50 views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \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 ...
0
votes
0answers
55 views

The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
1
vote
2answers
68 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 ...
2
votes
1answer
82 views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
0
votes
0answers
21 views

Linear Optimization: Minimizing number of CDs

I have 16 files I need to put on CDs with a capacity of 780 MBs. (240, 462, 117, 560, 379, 110, 341, 294, 503, 469, 90, 63, 617, 493, 524, and 396) How do i make a linear program to minimize the total ...
0
votes
1answer
36 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
2
votes
1answer
76 views

Linear Algebra 101 - Optimizing inequalities

I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality: $-4 \leq y < 4 \\ -9 \leq 2x + y \leq 9 \\ -9 \leq x + 2y \leq 9 \\ ...
0
votes
0answers
16 views

Deterministic equivalent construction

I have a 4-stage scenario tree. At each stage , i have two branches. So in total I have 15 nodes. I solve this problem in its node-variable formulation and it takes a lot of time. Also the ...
2
votes
0answers
23 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 ...
1
vote
1answer
14 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
0
votes
1answer
31 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
0
votes
2answers
40 views

Maximize $\ x+\frac32 y\ $ subject to…

I am stuck on the following problem: Consider the linear programming problem: Maximize $x+\frac32 y$ subject to $$2x+3y \le 16, \\ x+4y \le18,\\ x \ge 0,y \ge0.$$ If $S$ ...
1
vote
1answer
23 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
0
votes
0answers
35 views

Why does the Set Covering formulation perform worse?

For an assignment I have to allocate buses over bus trips such that all these trips are covered for a day, and minimize total costs. For this I have two different formulations, the Set Covering ...
0
votes
0answers
14 views

Linear Programming error bounds question

We have the LP problem: Maximize $P=3x+2y$ subject to $$-x+3y \leq 2+r_1$$ $$x+y \leq 8+r_2$$ $$2x-y \leq 10+r_3$$ What would be the formula for $P(r)$ in terms of $r=(r_1, r_2, r_3)$ for the ...
1
vote
0answers
23 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
0
votes
1answer
26 views

Computation time

I am implementing a mixed-integer linear programming problem, and I am dealing with an huge number of constraints. Does anyone know what the linear relation is between the number of constraints of ...
3
votes
1answer
36 views

How to reformulate this Set covering problem?

I am trying to solve the following implementation of the set covering problem of a crew rostering problem. Here constraint (19), meant to create a 12-hour break between the different shifts taken by ...
0
votes
0answers
31 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
0
votes
0answers
14 views

Objective Value of LP as a function of RHS of Constraints

I saw the following statement in a paper, but am having trouble finding a reference for it. Consider the optimization problem $y = \max_x c^\top x$ subject to $Ax = b$ and $x \ge 0$. Then, written as ...
1
vote
0answers
44 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
0
votes
1answer
85 views

can I get help in solving this equation using simplex method big-M method

Objective: $\max Z= 100x_1+300x_2+400x_3$ s.t. $10x_1+20x_2+30x_3≤1600$ $\;\,\quad10x_1+15x_2+20x_3≤1500$ $\;\,\quad x_2+x_3≤50$ $\;\,\quad x_1+x_2+x_3=70$ $\;\,\quad x_1,x_2,x_3≥0$
0
votes
0answers
59 views

How do I convert max min problem into a linear programming problem?

Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector. $$\max \min (c^T x - y^T Ax + b^Ty) \text{ such that } x,y \ge 0$$ Show that this problem can be reduced ...
2
votes
0answers
65 views

Post-optimality analysis: Change in one of the constraints

Consider the LP: max $\, -3x_1-x_2$ $\,\,$s.t. $\,\,\,\,$ $2x_1+x_2 \leq 3$ $\quad \quad \ -x_1+x_2 \geq 1$ $\quad \quad \quad \quad \ > x_1,x_2 \geq 0$ Suppose I have solved the above ...
2
votes
1answer
37 views

How do I solve max min (x − y) and min max (x − y) such that y≥0 and x≥0?

solve max min (x − y) and min max (x − y) such that y≥0 and x≥0 I don't have a clue where to start.
1
vote
1answer
45 views

Solving a minimization of the minimum problem

Let ${\bf c}_{1}$, ${\bf c}_{2}\in \mathbb{R}^{n}$, ${\bf A}\in\mathbb{R}^{m\times n}$ and ${\bf b}\in\mathbb{R}^{m}$. Show how one can solve the optimization problem: min ...
0
votes
0answers
21 views

How to pick the leaving variable for Perturbation method? (Linear programming)

I am studying Optimization, a math course. We are going over simplex method and its variances. One of which is called the perturbation method. From this example, O is the objective function and ...
2
votes
0answers
21 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 ...
1
vote
0answers
26 views

Optimizing over a set of optimization problems

This is my first time asking an optimization question on here, so I am looking forward to see what will happen here. In the lack of a better title, I wrote it as it is. At a high-level, I can perhaps ...
0
votes
1answer
23 views

making a function non-linear using a Lagrangian function

How Is this formula a Lagrangian function ? And how can a non-linear element be added to a function using this "Lagrangian function" This is where i got this In order to improve the performance ...
1
vote
0answers
39 views

Linear Programming, Optimal Solutions

I posted the whole question to give some context, but my problem lies with (iv). I think you're meant to use a formula for the generalization of the optimal solution, but I'm not really sure what ...
0
votes
0answers
27 views

Linear programming to find minimal additive and multiplicative factors

Consider samples $\{x_i,y_i\}$ with $x_i\in\mathbb{R}^N$ and $y_i=\pm1$ and additional $z\in\mathbb{R}^N$. Can one use linear programming to find the minimal $m>0$ and minimal $\epsilon>0$ (e.g. ...
0
votes
0answers
77 views

maximization function of a matrix given a scoring system

This is, from a mathematics standpoint, trivially solvable, but my goal is to solve it with the fewest number of comparisons. I'm hoping to discover that this problem is identical to something in ...
0
votes
1answer
27 views

Linear Inequalities - Allocation Problem

The problem at hand can be summarized as follows: we have to allocate a ressource to $n$ production units. The allocation to production unit $i$ is $x_i$. Each of the production unit will produce at ...
0
votes
0answers
20 views

Statistical Meaning of LP problem

What is the statistical interpretation of this LP problem for different values of $\mu$? $\min \sum_{j} \left( |x-b_j| + \mu (x-b_j) \right)$ I know that $\min \sum_{j} |x-b_j|$ is the median but ...
2
votes
0answers
47 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 ...
1
vote
1answer
52 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...