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

learn more… | top users | synonyms

1
vote
1answer
18 views

Degenerate solution in linear programming

How can I determine if a solution in a linear programming problem is degenerate without I use any software or the graphical display of the solution; For example in the model: $$\max\{2x_1 + 4x_2\}\\\...
0
votes
1answer
25 views

He makes $3$ products for his shop: large bowls, small bowls, and pots

He makes $3$ products for his shop: large bowls, small bowls, and pots. Each large bowl uses $3$ pounds of clay and $6$ fluid ounces of glaze. Each small bowl uses $2$ pounds of clay and $6$ fluid ...
0
votes
2answers
27 views

Linear equation in n variables with non negative solution

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
-1
votes
0answers
14 views

What determines the convergence time of a linear program?

I was wondering what are the properties of an LP problem or its the objective function that determine how fast CPLEX finds an optimum. To be specific, given a classical linear programming problem ...
1
vote
1answer
73 views

Can this optimization problem be solved?

I am working on an optimization problem but I am not sure if the problem can be formulated as an integer programming problem. Assume the cost minimization problem for a set of subscribers and ...
0
votes
2answers
80 views

Tableau and Simplex Method - No Calculator

A non-profit offers crafts complimentary gift packages for its donors. The non-profit costs for each package are \$4 for the Bronze level package, \$7 for the Silver level package, and \$9 for the ...
1
vote
2answers
89 views

Find min/max $\|x\|_{1}$ subject to $Ax = b$, using the simplex method

Let $Ax = b$ be a linear system with $a_{i,j} \in \{0,1\}$ and $b_i \in \{0,1,2,3,4,5,6,7,8\}$. The constraints on $x$ are $x_i \in \{0,1\}$. We suppose that the system admits at least one solution....
0
votes
0answers
27 views

Using the simplex method to find the minimum cost

A local food bank puts together complementary gift packages for its donors during their pledge drives. The bank's costs for each package are $\$4$ dollars for the Bronze level package, $\$7$ dollars ...
2
votes
2answers
946 views

Removing redundant linear constraints using Gaussian elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
2
votes
2answers
580 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? $\...
0
votes
0answers
28 views

silver bronze linear optimization

A non-profit offers crafts complimentary gift packages for its donors. The non-profit costs for each package are \$4 for the Bronze level package, \$7 for the Silver level package, and \$9 for the ...
3
votes
1answer
3k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ (...
1
vote
1answer
33 views

Maximization problem setup and analysis

So, I needed help in setting up the following: A coffee company sells two types of breakfast blends. They have on hand $132$ kg of dark roast and $84$ kg of hazelnut. One breakfast blend will ...
0
votes
1answer
69 views

Does this linear system have a single solution

Given unknown $x_1>0$, $x_2>0$, $x_3>0$, $x_4>0$, and known $y_1>0$, $y_2>0$, $y_3>0$, $y_4>0$, $$ \begin{cases} x_1+x_2=y_1 \\ x_1+x_4=y_2 \\ x_3+x_2=y_3 \\ x_3+x_4=y_4 \end{...
0
votes
1answer
420 views

Linear programming: Maximize minimum of linear functions

For a project I need something solved, it screams linear programming. If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
1
vote
0answers
32 views

Checking feasibility of a system of inequalities with scipy

I have a set of pairwise constraints, like this: a > b, b > c, c > a and need to check if they are satisfiable (in the example above, they are not). ...
0
votes
1answer
29 views

Linear program with ceiling or floor functions

Is it possible to solve a linear program where constraints have ceiling or floor functions applied to variables (with maybe some constants)? For instance: $$\lceil (x_1 + a)/b \rceil + \lceil (x_2 + c)...
0
votes
2answers
37 views

Break even methodology

Southeast Moldings molds plastic handles which cost $\$1.00$ per handle to mold. The fixed cost to run the molding machine is $\$3,640$ per week. If the company sells the handles for $\$4.00 $ each, ...
0
votes
0answers
19 views

Geometric interpretation of linear programming dual

Is there a geometric interpretation of the linear programming dual in terms of the primal? I feel like without some sort of intuition of it, I don't truly understand it.
3
votes
2answers
33 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,...
0
votes
1answer
36 views

Why isn't Linear Programming less convoluted? [Soft Question]

Just a quick question. So I'm taking a course in linear optimization, and one of the things that we're going over obviously is the simplex method. I just started the class so I may not be seeing the ...
2
votes
2answers
70 views

How to covert min min problem to linear programming problem?

I have the following problem: set $P=\{1,2,3...,n\}$ for index $i$, set $K=\{1,2,3,...,m\}$ for index $k$. Value $B_i^k$ is indexed by both $i$ and $k$, while value $l_i$ is indexed by only $i$. Here ...
0
votes
1answer
24 views

All-sizes Network Simplex

I am currently using Network Simplex to find the min-cost flow to send $x$ units of goods from source $s$ to sink $t$ given a capacitated graph. I would now like to solve the problem for all $x \in [...
0
votes
0answers
38 views

Finding shortest vertical segment connecting two sets of intersecting half-planes

Consider two sets of $n$ half-planes each. Denote the sets by $A$ and $B$. How can we find a vertical segment $s$ of a minimum length such that the upper end of $s$ is in the intersection of $A$ and ...
1
vote
1answer
41 views

Linear programming with a product term in the objective function

The title might sound a little weird. I actually want to ask if this problem can be solved as a LP. And if so, how to convert the product term? set $P=\{1,2,3,\ldots,n\}$ for index $i$. Variables $...
1
vote
1answer
4k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
2
votes
0answers
36 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:...
2
votes
1answer
22 views

Model cost for a state change in an integer program

I have a problem involving tool selection I am trying to model right now. (I am fairly new to this). I have a series of manufacturing operations I need to perform for $i \in \{1,\dots,n\}$. Each ...
1
vote
1answer
24 views

Existence of solution to underdetermined linear system with variable coefficient matrix.

I'm trying to think through a network flow problem, and while I could probably shuffle this into a form that a linear programming method would work, it feels like there ought to be something more ...
0
votes
1answer
20 views

Will the slack variables always have coefficients of zero in the objective function?

I've been following this video: https://www.youtube.com/watch?v=M8POtpPtQZc Will the CBi values (slack variable coefficients) ever not be zero? When?
-2
votes
0answers
19 views

Linear programming model to maximize profit [closed]

Operation A B grinding. 1. 2 Turning. 3. 1 Assembling. 6. 3 Testing. 5. 4 Operations in hours for a given time period are ...
0
votes
1answer
20 views

Convert this problem into linear programming format

This problem is from the book Luenberger "Linear and Non Linear Optimization". I am facing difficulty with this problem. I am trying to follow this logic - Let $t = \max (c_1^Tx+d_1,....,c_p^Tx+d_p)$...
0
votes
0answers
17 views

Solve $\max_{\lambda} \mathrm{sum} (\lambda \vec{u} \geq_c \vec{v})$

Let $\vec{u},\vec{v} \in R^n$ be known vectors. I want to find out the optimum scalar multiplier $\lambda$, to maximize the number of elements in $\lambda \vec{u}$ which are above $\vec{v}$. In other ...
2
votes
2answers
55 views

Sensitivity analysis in linear programming

Could someone please explain in detailed steps how to apply a sensitivity analysis to such problem: $$maximize \ \ 2x_1 + 3x_2 \\ s.t. \ \ 4x_1+3x_2≤600 \\ 2x_1+2x_2≤320 \\ 3x_1+7x_2≤840 \\ x_i≥0$$ ...
1
vote
1answer
416 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < N$...
2
votes
2answers
36 views

LP: add extra costs in the objective function for every variable which is not equal to $0$

I am trying to optimise an LP problem but extra costs should be added if a variable is larger than $0$. For example, if we have the following objective function: $$\text{minimize} \qquad 2X_1 + 3X_2 ...
0
votes
1answer
82 views

Necessary condition for existence of a positive solution of a linear system

I would like to know what are the necessary conditions of existence of a positive (componentwise) solution of the system : Ax=b, with A a square ...
1
vote
3answers
77 views

Binary integer variables in linear programming

Could someone please explain the concept of switch variables (binary integer decision variables) in linear programming? This example has two alternative constraints $$\begin{array}{ll} \text{...
0
votes
0answers
15 views

Solve $\max_X \mathrm{sum}(AXB \geq \gamma)$, with $X$ being a permutation matrix

I have a problem to find the best permutation matrix $X \in \{0,1\}^{n \times n}$, which would maximizes the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
1
vote
0answers
17 views

Find optimum diagonal matrix $D$ to maximize $ADB$ above a threshold $\gamma$

I have a problem to find the optimum diagonal matrix $D$, which would maximizes the number of elements in $ADB$ which are above a certain positive number $\gamma$. In other words, the problem is ...
0
votes
1answer
683 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...
0
votes
0answers
14 views

Finding Dual of non-standart programming problem

I am working in optimization field. My programming problem is not of the standart form, however it is convex. Objective is nonlinear but concave (log of product). I do maximization. Constaints: ...
0
votes
1answer
35 views

simplex method tableau

If I have the matrix: x1 x2 s1 s2 s3 z 1 4 1 0 0 0 | 12 2 5 0 1 0 0 | 2 1 3 0 0 0 1 | 4 ---------------- -2 -1 0 0 0 1 | 0 Then, where x1 is the row of 1, 2, 1....x2 is the row of 4, 5, 4.......
3
votes
0answers
276 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 $\...
0
votes
0answers
43 views

Coefficient variation in Objective Function in Mixed Integer programming

Assume we have the following Mixed Integer programming. MIP 1) $Z1=$ Max $Ax+By$ s.t $Cx+Dy<=E$ $x>=0$ and $y: {0,1}$ Now, assume we have the same MIP, and I just converted A to A' MIP2)...
0
votes
0answers
18 views

Find permutation matrix $X \in \{0,1\}^{N \times N}$ in order to make $XAX \geq_c B$

I need to solve a problem to find out the best permutation matrix $X \in \{0,1\}^{N \times N}$ which would maximize the number of elements in matrix $XAX$ which are above (component-wise) matrix $B$ ...
1
vote
1answer
39 views

Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system \begin{equation} y = A_1 x_1 + A_2 x_2 \end{equation} subject to the linear constrains \begin{equation} C_1 x_1 + C_2 x_2 \leq d \end{equation} I am looking ...
1
vote
1answer
150 views

Linear programming with non-convex quadratic constraint

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard? $\min c^Tx$ s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in \mathbb{R}_+^n,Q\in\...
6
votes
1answer
644 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
0answers
22 views

simplex method for minimal

Use the simplex method to solve the following linear programming problem. Find y1≥0 and y2≥0 such that 2y1 + 2y2 >= 13, y1 + 2y2 ≥13​, and w=3y1 +18y2 is minimized. I'm trying to find the minnimum of ...