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
4
votes
2answers
154 views

Any Solution for $k$-means with minimum and maximum cluster size constraint?

I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster. $N$ be the number ...
2
votes
1answer
69 views

How to linearize inequalities having max or min?

I'm modeling an LP problem in which I have to maximize an objective function. Two of the constraints are the following, where $k_i$ are constants and $x_i$ decision variables (continuous). Could ...
5
votes
4answers
443 views

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
2
votes
2answers
98 views

How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables?

I'm modeling an optimization problem in which a decision variable $x_1$ in the objective function depends on if-else conditions involving decision variables $x_2$ and $x_3$, as the following equation, ...
4
votes
1answer
321 views

Is there any automatic way to spot contradictory constraints in linear programming?

Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align} It's easy ...
4
votes
1answer
63 views

Name for subclass of ILP without any inequality constraints (including constraints on x)

In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says: The problem of finding $x\in \mathbb{Z}$ such that $Ax=b$, where $A\in\mathbb{Z}^{m\times n}$ ...
1
vote
0answers
65 views

LP instead of IP formulation of assignment problem

In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation: ...
4
votes
3answers
111 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
149 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
2answers
185 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 ...
2
votes
3answers
135 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. ...
0
votes
1answer
266 views

How to mathematically formulate the optimization problem?

I have a system with $S$ service points. There are also $U$ users in the system. We have $$U>S>G$$ One group can have maximum $M$ service points, but there is no restrictions on the number of ...
1
vote
1answer
141 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
84 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
98 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 ...
6
votes
2answers
317 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
39 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
99 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
85 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
127 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
41 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
65 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
128 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
114 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
644 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
46 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
101 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
250 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_{...
3
votes
2answers
316 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 ...
4
votes
1answer
225 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 ...
2
votes
0answers
47 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
40 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
169 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
359 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
69 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
122 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
52 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
65 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
48 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 ...
3
votes
2answers
115 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
94 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) $$ \...
2
votes
1answer
48 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
229 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
68 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
60 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 ...
6
votes
3answers
936 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
45 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
196 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
88 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
81 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 ...

1
2
3 4 5
8