Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
2
votes
1answer
14 views

warmstarting simplex algorithm- how much can problems differ from each other?

I'm working on an implementation of the simplex algorithm. I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem. I couldn't really say ...
1
vote
1answer
116 views

How to linearize the product of a binary and a continuous variable? [duplicate]

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
4
votes
1answer
88 views

Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)

I am trying to write a program to schedule a team of 8 individuals into shifts. I want to know how to model that every individual must get at least one night shift break, and must not work two ...
-4
votes
0answers
40 views

What will be an efficient heuristic approach for this optimization problem

I am looking for a heuristic approach to this optimization problem. How to mathematically formulate the optimization problem? RobPratt suggested an mathematical formulation for this problem which is ...
2
votes
3answers
115 views

Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ...
1
vote
1answer
117 views

How to mathematically formulate the optimization problem?

I have a system with $S$ service points. There are also $U$ users in the system. The service points as well as users need to be grouped in $G$ non overlapped groups. Therefore, one user/service point ...
0
votes
1answer
70 views

Mixed Integer Programming - How to model the dependency of two variables in an objective function

I have two variables $a$ and $b$, in which $a$ is the amount of goods and $b$ is the amount of boxes of the given sizes. So $b$ (box size + number) is dependent on a (goods quantity). If $a$ is ...
3
votes
0answers
70 views

How to linearize a max min objective function?

Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables: $\underset{x}\max \underset{y}\min dy$ Associated with the linear set of constraints and right ...
1
vote
1answer
69 views

Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time

I want to solve a job shop scheduling problem. I got $n$ Jobs that have to be scheduled on $k$ Machines. A Job $i$ has 2 or 3 Tasks $j$, and there is a known sequence of the Tasks of a Job. One ...
3
votes
0answers
100 views

0 1 solution of linear programming problem with only equality constraints

I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
0
votes
0answers
35 views

linear equation with conditions in Java

I have the following problem: I want to determine a linear equation for a data table with $x$ and $y$ value. Point 1 should be the point where the first time $y > 0$ and point 2 should be the point ...
1
vote
1answer
88 views

complexity order of the interior point method

I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5? Much appreciate your time and consideration.
0
votes
1answer
76 views

How to linearise this nonlinear constraint?

I have a constraint in the form $\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$ where $x_{m,n}$ is binary variable $t_u$ and $\beta_u$ are continuous optimization ...
1
vote
1answer
86 views

How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

I have an objective function as follows $\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
0
votes
0answers
40 views

Linear equation from pairs of values with conditions in Gurobi (Java)

How can I create a linear equation in Gurobi (Java) from values (x-y value pairs) that also has the following properties: $\forall x \leq 0 \Longrightarrow y = 0$ The linear line/equation should have ...
2
votes
1answer
60 views

Constraining flow into a node and out of a node using Min Cost Flow input

Let's say I have a graph $G=(V,E)$ where each vertex has an edge going both into and out of it (i.e. cyclic, akin to the kidney donor pair problem). Now suppose we have a capacity $u_{ij} = 1 \forall(...
3
votes
1answer
105 views

Min Cost Flow with lower bound reduction to MCF algorithm

We define the Min Cost Flow Problem with Lower Bounds (MCFPLB) as a generalization of the usual Min Cost Flow. The input consists of: a directed graph $G=(V,E)$ capacities $u_{ij} \geq 0$ for each ...
2
votes
1answer
110 views

Can I solve the separation problem efficiently, when I have access to an optimization oracle?

Assume I have given a convex feasible set $X$ and I have an oracle that can optimize some linear objective function $c$ over $X$. Assume that I have given a point $r$. I want to solve the separation ...
10
votes
2answers
622 views

Do LP solvers convert LPs to standard form?

To solve a linear program (LP) using the simplex method one first needs to bring the LP to standard form. This requires replacing every equality constraint with two inequalities and replacing every ...
1
vote
0answers
44 views

Unifying constraint matrices in sparse situations

$\DeclareMathOperator\Set{Set}$ Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$. I am trying to write $$ Set=\{x\in\...
3
votes
0answers
99 views

Two binding constraints - Linear Programming

I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
4
votes
3answers
213 views

Clustering points based on a distance matrix

Although I asked this question on stackoverflow to possibly reach a broader audience, I wonder your inputs about this problem. Without giving much research into this, I thought p-center problem ($x_{...
2
votes
1answer
257 views

If-then constraint with continuous variables

I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ...
3
votes
1answer
218 views

Algorithms for sparse linear systems

I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems? The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make ...
1
vote
0answers
44 views

To estimate new sales from history

A fruit supplier sells 3 types of fruits. The company has 3 salespersons. Here are the sales quantity of each person for each fruit. The total sales figure is available. (this is all the available ...
3
votes
0answers
32 views

PuLP Python: How to linearize an inequality involving an integer variable

I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T. The total amount of payable tonnes i.e. what the customer will ...
1
vote
1answer
51 views

How to dynamically set variable names in Pyomo?

I am looking to set variables in my Pyomo model by using a loop, so that they can be created automatically. However, each variable also contains bounds. I was hoping that it can loop through a ...
4
votes
2answers
206 views

Two-Objective Optimization in CPLEX

Until now, I used CPLEX to solve single-objective optimization problems only, but now I need to solve a two-objective mixed-integer linear optimization problem and I noticed that CPLEX 12.6.9 (unlike ...
1
vote
0answers
65 views

Decomposition of Polyhedra

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
4
votes
1answer
69 views

How to convert static variables into arrays for use with PuLP

I have the following code in Python and PuLP which uses static variables. I want to know how to solve the problem by converting all of the LpVariable parts into an array, as well as the constraints. ...
3
votes
0answers
51 views

Where I can study some job shop scheduling by course (video )?

I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver by some course/video as I see some of books and papers hard to understand . It is hoped that the ...
1
vote
0answers
63 views

How to start the Dantzig-Wolfe decomposition?

I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
0
votes
1answer
43 views

Adding slack nodes to min cost network flows

I have the following question. I want to clarify couple of points. As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is: Do we need to ...
2
votes
2answers
98 views

Multi-objective function normalization

I am trying to solve the multi-objective function of my linear program. Are there another approaches other than the weighted sum approximation?
2
votes
0answers
72 views

Solving transportation problem by the Network Simplex

I am trying to solve the following problem using Network Simplex method. But I have questions. My attempt: Basis Matrix$(B)$ Rows: 1, 2, 3, 4, 5 Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) $$ \...
1
vote
1answer
41 views

Maximum flow minimum cut

For the following problem I am trying to find maximum flow and minimum cut: I found the maximum flow as 6 like this: $1-3-7-8:2 flows$ $1-2-5-8: 2 flows$ $1-3-4-5-8:1 flow$ $1-3-4-6-5-8:1 flow$ But I ...
4
votes
1answer
191 views

Column generation for a linear optimization problem

I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
1
vote
1answer
57 views

$i \neq j$ as a linear constraint where variables are binary

Let $i$ and $j$ be two binary variables. How can I express $i \neq j$ as a linear constraint?
0
votes
1answer
51 views

Minimum cost flow problem with negative cost arcs

As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc ...
5
votes
3answers
918 views

How do you take into account order in linear programming?

How do you write order in a linear program? For instance, you want to arrange red and blue marbles labelled 1 – 30 each, and you would want to arrange it in ascending order, you cannot have red ...
1
vote
0answers
33 views

Vertices of Polytope using Gurobi

Is there any way I can obtain all the vertices of a polytope using Gurobi? If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
3
votes
2answers
179 views

Modeling in integer programming vs modeling in constraint programming

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams). Now I am trying to learn how to model with constraint programming. ...
3
votes
1answer
78 views

In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?

I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices. I have trouble ...
1
vote
1answer
76 views

How can I formulate an objective function that minimises the number of items required to solve a problem

I am currently trying to solve a problem where I need to minimise transport cost through the choice of vehicle (and how many of each choice) subject to a given demand. The problem: There are currently ...
3
votes
1answer
52 views

Strict inclusion for facility location formula and aggregate facility location formula

I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
2
votes
0answers
70 views

How to linearize this multiplicative constraint?

I have a constraint in the form $\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$ Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable). $x$ and $\zeta$ are also optimization ...
2
votes
1answer
97 views

Defining Solution Space in MILP / LP using If Then Statements

I have the following statements for an MILP: Variables: $c$ (can be $1$ or $0$); $\alpha_j$ (real numbers with $0\le\alpha_j\le1$). I have a linear inequality system for $\alpha_j$: $\sum_jv_j\...
13
votes
3answers
2k views

How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms

As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class ...
8
votes
4answers
520 views

Algorithm for simplifying a set of linear inequalities

I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of ...
-2
votes
1answer
63 views

How can I model this Hyperbolic constraint?

In this problem, $\beta_u$, $w_{u,c}$ (a vector of complex elements), $x_u$ are optimization variables. Now, $||2\sqrt{\frac{\pi_u}{2}}\beta_u; h_{u,c}^{\rm H}w_{u,c}-\frac{1}{2\pi_u}x_u-1||_2\le h_{u,...

1
2 3 4 5
7